E. Любитель кроссвордов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Олег Петрович любит кроссворды и каждый четверг покупает в газетном киоске свой любимый журнал с кроссвордами и разными словесными головоломками. В последнем выпуске Олег Петрович обнаружил интересную головоломку, за решение которой в журнале обещали ценный приз. Ниже мы приводим её формальное описание.

Поле для головоломки состоит из двух рядов по n клеток в каждом. Каждая клетка содержит ровно одну строчную английскую букву. Нужно найти и вычеркнуть на этом поле некоторое данное слово w, состоящее из k строчных английских букв. Решением головоломки является последовательность клеток поля c1, ..., ck, такая что:

  • Для всех i от 1 до k буква, записанная в клетке ci, совпадает с буквой wi;
  • Все клетки в последовательности попарно различны;
  • Для всех i от 1 до k - 1 клетки ci и ci + 1 имеют общую сторону.

Олег Петрович быстро нашёл решение для головоломки. Теперь ему интересно, сколько для нее существует различных решений. Олег Петрович не любит слишком большие числа, поэтому посчитайте ответ по модулю 109 + 7.

Два решения ci и c'i считаются различными, если последовательности клеток не совпадают хотя бы в одной позиции, то есть найдётся такое j от 1 до k, что cj ≠ c'j.

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

В первых двух строках записано состояние поля для головоломки. Каждая из этих строк непустая и содержит по n маленьких латинских букв.

Следующая строка оставлена пустой.

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

Длина каждой из строк не превосходит 2 000.

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

Выведите одно целое число — количество решений головоломки по модулю 109 + 7.

Примеры
Входные данные
code
edoc

code
Выходные данные
4
Входные данные
aaa
aaa

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