- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر
آقای مهندس در اتاق مدیریت خود گاوصندوق بزرگی دارد که همهی اسرار بزرگ شرکت در آن نگهداری میشود. یک گاوصندوق بزرگ برای امنیت هرچه بیشتر نیاز به یک رمز خیلی بزرگ هم دارد. آقای مهندس ارقام رمز گاوصندوقش را، که یک عدد طبیعی خیلی بزرگ است، پشتسرهم روی یک تکه کاغذ دراز نوشته و آنرا همیشه در جیب کتش نگه میدارد.
بچهی آقای مهندس که امروز در مهدکودک کار با قیچی را برای ساختن کاردستی یاد گرفته، با دیدن کاغذ رمز گاوصندوق در جیب پدرش بسیار شگفتزده میشود و آن را به \(n\) قطعه تقسیم میکند. (او همهی برشهایش را عمودی و بین ارقام میزند، طوری که هیچ رقمی خراب نشود و در هر تکه از کاغذ تعدادی از ارقام پشتسرهم رمز قرار بگیرد)
آقای مهندس وقتی رمز را تکهتکه میبیند، آرامش خود را حفظ میکند، و سعی میکند رمز گاوصندوق را بازسازی کند. اما تنها این را به یاد دارد که رمز بر \(11\) بخشپذیر بودهاست، زیرا همانطور که میدانید \(11\) عدد مورد علاقهی خانم دکتر است. حال او از شما میخواهد با گرفتن اعداد نوشتهشده روی تکههای کاغذ به او بگویید که در چند حالت چیدن تکههای کاغذ کنار هم یک رمز ممکن برای گاوصندوق درست میشود. (یعنی رمز بر \(11\) بخشپذیر میشود)
ورودی
در سطر اول ورودی عدد طبیعی \(n\)، تعداد قطعات کاغذ آمده است. در خط بعد اعداد طبیعی \(a_1\) تا \(a_n\) آمده است که \(a_i\) عدد نوشتهشده در کاغذ \(i\)ام را نشان میدهد. تضمین میشود که هیچکدام از اعداد ورودی در ابتدای خود \(0\) ندارند. (leading zero ندارند).
\[1 \le n \le 2\ 000\]
\[1 \le a_i \le 1\ 000\ 000\]
خروجی
در خروجی تعداد حالتهایی از چیدن قطعات (از مجموع \(n!\) حالت) که یک رمز ممکن برای گاوصندوق میسازند را چاپ کنید. (باقیمانده بر \(10^9+7\))
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۰ | \( n \le 20 \) |
| ۲ | ۱۰ | \( n \le 200 \) , \(1 \le a_i \le9\) |
| ۳ | ۵ | \( n \le 200 \) , \(10 \le a_i \le 99\) |
| ۴ | ۳۵ | \( n \le 200 \) |
| ۵ | ۴۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
5
11 11 11 11 11
خروجی نمونه ۱
120
ورودی نمونه ۲
7
10 20 3 15 1000 60 16
خروجی نمونه ۲
336
(۲۴امین دوره المپیاد کامپیوتر - آزمون سوم - ۱۳۹۳/۰۶/۰۶)