Стиснутий статус#2823

Стиснутий статус

1 секунда

64 мегабайти

Дуже легка

Деякі інженери втомилися від багатьох різних способів кодування статусних повідомлень, тому вирішили винайти власну систему. У їхній схемі закодоване статусне повідомлення складається з послідовності цілих чисел, кожне з яких представляє символ повідомлення, розділених пробілами. Кожне число знаходиться у межах від $1$ до $M$ включно. На жаль, вони вирішили стиснути закодовані повідомлення, видаливши всі пробіли!

Ваше завдання — визначити, скільки різних оригінальних закодованих статусних повідомлень могло привести до даного стиснутого повідомлення. Оскільки це число може бути дуже великим, виведіть відповідь по модулю $4207849484$ ( $0 x f a ce b 00 c$ 0xfaceb00c у шістнадцятковій системі).

Наприклад, якщо стиснуте повідомлення — це $12$ , то початкове повідомлення могло бути $12$ або $12$ . Довжина стиснутих повідомлень знаходиться у межах від $1$ до $1000$ символів включно.

Вхідні дані

Перший рядок містить одне ціле число $N$ ( $1 \leq N \leq 25$ 1 \le N \le 25) — кількість стиснутих статусних повідомлень, які потрібно проаналізувати. Кожен з наступних $N$ рядків містить ціле число $M$ ( $2 \leq M \leq 255$ 2 \le M \le 255), найбільший код символу у базі, а також стиснуте повідомлення. Усі елементи у вхідних даних розділені пробілами. Гарантується, що $1 \leq$ довжина кожного стиснутого повідомлення $\leq 1000$ .

Вихідні дані

Для кожного тесту, у порядку від $1$ до $N$ , виведіть рядок Case #i:, а потім одне ціле число — кількість різних закодованих статусних повідомлень, які могли б відповідати цій стиснутій послідовності. Якщо жодне повідомлення не можливе, виведіть $0$ .

Приклади

Приклад 1