B. Одержимость строкой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вам дана строка s. Сколько существует способов извлечь k ≥ 1 неперекрывающихся подстрок из неё, таких, что в каждой из них содержится t как подстрока? Более формально, требуется подсчитать количество способов выбора двух последовательностей, a1, a2, ..., ak и b1, b2, ..., bk, удовлетворяющих следующим требованиям:

  • k ≥ 1
  •   t является подстрокой строки saisai + 1... sbi (строка s индексируется с 1).

Так как количество способов может быть очень большим, выведите его по модулю 109 + 7.

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

Ввод состоит из двух строк s и t (1 ≤ |s|, |t| ≤ 105). Каждая строка состоит из маленьких букв латинского алфавита.

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

Выведите ответ единственной строкой.

Примеры
Входные данные
ababa
aba
Выходные данные
5
Входные данные
welcometoroundtwohundredandeightytwo
d
Выходные данные
274201
Входные данные
ddd
d
Выходные данные
12