ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Неотсортированные > задача:


Демоническое программирование

Задачи раздела

• Даты: интервал между датами
• Даты: конструктор
• Даты: конструктор по номеру
• Даты: номер дня в году
• Девятеричное сложение
• Деление длинного числа на короткое
• Делители
• Демоническое программирование
• Демоническое программирование
• День рождения
• Деревья
• Дисперсия последовательности
• Длинная сумма
• Длинное произведение
• Длинный НОД
• Довольно грустная задача
• Довольно грустная задача (услож...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Демоническое программирование
Демоническое программирование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Димон решил, что ему нужно стать крутым олимпиадным программистом, чтобы побеждать в соревнованиях, выигрывать призы и угнетать всяких туристов. Первым делом, считает Димон, надо изобрести свою собственную технологию программирования. Спустя полчаса новейшая, не имеющая аналогов в мире технология была готова. Димон скромно решил назвать своё детище «димоническим программированием», но Word подчеркнул первое слово, и в итоге название было изменено на «демоническое программирование».

Запись всех команд демонического программирования состоит из нулей и единиц, ведь Димон знает, что все крутые программисты работают с нулями и единицами. Кроме того, Димон решил добавить демонические символы — латинские буквы A и B, чтобы команды стали ещё круче и пафоснее. В итоге среди команд могут оказаться, например, такие: 0010, 11A101, BBA000.

Димон составил список всех возможных команд демонического программирования и даже написал программу, после чего, довольный, пошёл спать. Дело оставалось за малым — научить все компьютеры понимать команды демонического программирования, но уж с этим Димон как-нибудь разберётся.

На следующий день, рассматривая свою первую программу, Димон вдруг понял, что у неё может быть несколько разных смыслов! Ещё бы — ведь все команды Димон записывал в одну строку, без пробелов (да-да, потому что все крутые программисты так делают).

Помогите Димону узнать, сколькими разными способами можно разделить его программу на отдельные команды.

Входные данные

Первая строка содержит целое число N (1 ≤ N ≤ 20) — число команд демонического программирования.

Следующие N строк описывают команды. Каждая из них содержит строку Ci (1 ≤ |Ci| ≤ 10), состоящую из символов 0, 1, A, B, — запись команды. Все команды различны.

Следующая строка содержит строку P (1 ≤ P ≤ 100), состоящую из символов 0, 1, A, B, — запись программы Димона.

Выходные данные

Выведите одно целое число — количество способов разложения программы на последовательность команд. Так как ответ может оказаться очень большим, выведите остаток от его деления на 1000000007.

Примеры

Входные данные
4
0
1
01
11
101100101
Выходные данные
12
Входные данные
3
0A
1B
AB
1BAB0ABAB
Выходные данные
0

Для отправки решений необходимо выполнить вход.

www.contester.ru