سوال ۲

آقای مهندس در اتاق مدیریت خود گاوصندوق بزرگی دارد که همه‌ی اسرار بزرگ شرکت در آن نگه‌داری می‌شود. یک گاوصندوق بزرگ برای امنیت هرچه بیشتر نیاز به یک رمز خیلی بزرگ هم دارد. آقای مهندس ارقام رمز گاوصندوق‌ش را، که یک عدد طبیعی خیلی بزرگ است، پشت‌سرهم روی یک تکه کاغذ دراز نوشته و آن‌را همیشه در جیب کت‌ش نگه می‌دارد.

بچه‌ی‌ آقای مهندس که امروز در مهدکودک کار با قیچی را برای ساختن کاردستی یاد گرفته،‌ با دیدن کاغذ رمز گاوصندوق در جیب پدرش بسیار شگفت‌زده می‌شود و آن را به n قطعه تقسیم می‌کند. (او همه‌ی برش‌هایش را عمودی و بین ارقام می‌زند، طوری که هیچ رقمی‌ خراب نشود‌ و در هر تکه از کاغذ تعدادی از ارقام پشت‌سرهم رمز قرار بگیرد)

آقای مهندس وقتی رمز را تکه‌تکه می‌بیند، آرامش خود را حفظ می‌کند، و سعی می‌کند رمز گاوصندوق را بازسازی کند. اما تنها این را به یاد دارد که رمز بر $11$ بخشپذیر بوده‌است، زیرا همان‌طور که می‌دانید $11$ عدد مورد علاقه‌ی خانم دکتر است. حال او از شما می‌خواهد با گرفتن اعداد نوشته‌شده روی تکه‌های کاغذ به او بگویید که در چند حالت چیدن تکه‌های کاغذ کنار هم یک رمز ممکن برای گاوصندوق درست می‌شود. (یعنی رمز بر $11$ بخشپذیر می‌شود)

• در سطر اول ورودی عدد طبیعی $n$، تعداد قطعات کاغذ آمده است. در خط بعد اعداد طبیعی $a_1$ تا $a_n$ آمده است که $a_i$ عدد نوشته‌شده در کاغذ $i$ام را نشان می‌دهد.
• $1 \leq n \leq 2000$
• $1 \leq a_i \leq 10^6$
• تضمین می‌شود که هیچ‌کدام از اعداد ورودی در ابتدای خود $0$ ندارند. (leading zero ندارند)

در خروجی تعداد حالت‌هایی از چیدن قطعات (از مجموع $n!$ حالت) که یک رمز ممکن برای گاوصندوق ‌می‌سازند را چاپ کنید. (باقی‌مانده بر $10^9 + 7$)

• زیرمسئله اول (۱۰ نمره): $n \leq 20$
• زیرمسئله دوم (۱۰ نمره): همه‌ی اعداد نوشته‌شده روی کاغذ‌ها یک‌رقمی هستند. ($1 \leq a_i \leq 9$) و $n \leq 200$
• زیرمسئله سوم (۵ نمره): همه‌ی اعداد نوشته‌شده روی کاغذ‌ها دورقمی هستند. ($10 \leq a_i \leq 99$) و $n \leq 200$
• زیرمسئله چهارم (۳۵ نمره): $n \leq 200$
• زیرمسئله پنجم (۴۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل