کارآگاه آرین و قفل مرگبار

بعد از هفته‌ها تعقیب و تحقیق، کارآگاه مشهور، آرین، بالاخره تلفن همراه قاتل سریالی را پیدا کرد.
اما فقط یک مشکل باقی مانده است...

گوشی با یک قفل الگویی (Pattern Lock) محافظت می‌شود؛ همان الگویی که با کشیدن انگشت روی صفحه رسم می‌شود و عددی تایپ نمی‌شود.
اعداد روی تصویر فقط برای مشخص کردن جایگاه نقاط هستند.

آرین با استفاده از دستگاه تحلیل اثر انگشت متوجه شده بعضی از نقاط صفحه حتماً در الگو لمس شده‌اند.
حالا او باید قبل از پاک شدن اطلاعات گوشی، تعداد تمام الگوهای ممکن را پیدا کند.

صفحه‌ی قفل به شکل زیر است:

1 2 3
4 5 6
7 8 9

قوانین الگو:

• هر عدد حداکثر یک بار می‌تواند در الگو ظاهر شود.
• ترتیب لمس اعداد مهم است.
• هنگام حرکت بین دو عدد، ممکن است دقیقا یک عدد در وسط مسیر آن‌ها قرار داشته باشد.
  • اگر آن عددِ وسط قبلاً در الگو دیده شده باشد، حرکت مستقیم مجاز است.
  • در غیر این صورت، آن عدد نیز هنگام حرکت لمس شده و به الگو اضافه می‌شود.

مثال‌ها:

• بین 1 و 3 عدد 2 در وسط قرار دارد.
• بین 1 و 9 عدد 5 در وسط قرار دارد.
• بین 1 و 7 عدد 4 در وسط قرار دارد.

برای مثال، در حرکت 1 → 3:

• اگر 2 قبلاً دیده شده باشد، فقط 3 لمس می‌شود.
• وگرنه مسیر از روی 2 عبور کرده و 2 نیز به الگو اضافه می‌شود.

به آرین کمک کنید تعداد الگوهای معتبری را پیدا کند که تمام اعداد داده‌شده را حداقل یک بار لمس کنند.