G. Тайные слова
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сирин переместился в параллельный мир, и Сказочному патрулю надо отправляться за ним.

Снежка подошла к старому камину и заметила, что за кирпичом торчит уголок какого-то старого свитка. Она осторожно вытащила его и развернула. На пергаменте был написан сплошной поток непонятных букв и символов, а рядом лежал небольшой листок со списком загадочных слов.

Девочки поняли, что это ещё один шифр Сирина. На краю листа была пометка — «Тем, кто хочет добраться до параллельного мира, нужно разбить весь текст на отдельные тайные слова из этого списка. Каждое слово можно использовать любое число раз, но ничего лишнего добавлять нельзя. Учтите: символы «?» в тексте заменяют любые буквы тайного слова».

Маша, взглянув на текст, который достала Снежка, поняла, что этот текст можно разбивать на слова множеством способов! Как же узнать, сколько всего таких способов существует? Она поняла, что придется считать. Но самим девочкам это, похоже, не осилить — нужна ваша помощь!

Помогите девочкам из Сказочного патруля догнать Сирина — определите, сколько существует различных способов разбить текст из пергамента на тайные слова из листочка.

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

В первой строке дано целое число $$$n$$$ $$$(1 \le n \le 100)$$$ — число тайных слов.

Каждая из следующих строк содержит строку $$$W_i$$$ $$$(1 \le |W_i| \le 10)$$$ — $$$i$$$-е тайное слово.

Гарантируется, что все слова $$$W_i$$$ уникальны, то есть для $$$i \ne j$$$ выполняется $$$W_i \ne W_j$$$.

Последняя строка содержит строку $$$T$$$ $$$(1 \le |T| \le 100)$$$ — текст из пергамента.

Гарантируется, что

  • каждое слово $$$W_i$$$ состоит только из букв латинского алфавита в нижнем регистре (a — z);
  • текст $$$T$$$ состоит только из букв латинского алфавита в нижнем регистре (a — z) и символов «?», где каждый символ «?» заменяет ровно одну произвольную букву.
Выходные данные

Пусть $$$P$$$ — количество способов разбиения текста из пергамента на тайные слова.

В единственной строке выведите единственное целое число — остаток от деления $$$P$$$ на $$$M = 10^9 + 7$$$.

Примеры
Входные данные
7
a
b
c
d
ab
bc
cd
ab?d
Выходные данные
11
Входные данные
2
a
b
??
Выходные данные
4
Примечание

Первый тестовый пример

Перечислим возможные способы разбиения текста:

  1. $$$[\texttt{a}, \texttt{b}, \texttt{a}, \texttt{d}]$$$;
  2. $$$[\texttt{a}, \texttt{b}, \texttt{b}, \texttt{d}]$$$;
  3. $$$[\texttt{a}, \texttt{b}, \texttt{c}, \texttt{d}]$$$;
  4. $$$[\texttt{a}, \texttt{b}, \texttt{d}, \texttt{d}]$$$;
  5. $$$[\texttt{ab}, \texttt{a}, \texttt{d}]$$$;
  6. $$$[\texttt{ab}, \texttt{b}, \texttt{d}]$$$;
  7. $$$[\texttt{ab}, \texttt{c}, \texttt{d}]$$$;
  8. $$$[\texttt{ab}, \texttt{d}, \texttt{d}]$$$;
  9. $$$[\texttt{a}, \texttt{bc}, \texttt{d}]$$$;
  10. $$$[\texttt{a}, \texttt{b}, \texttt{cd}]$$$;
  11. $$$[\texttt{ab}, \texttt{cd}]$$$.

Второй тестовый пример

Перечислим возможные способы разбиения текста:

  1. $$$[\texttt{a}, \texttt{a}]$$$;
  2. $$$[\texttt{a}, \texttt{b}]$$$;
  3. $$$[\texttt{b}, \texttt{a}]$$$;
  4. $$$[\texttt{b}, \texttt{b}]$$$.