Хамед недавно нашел строку t и неожиданно для себя крепко к ней привязался. Несколько дней он пытался найти все вхождения t в другие имеющиеся у него строки. Наконец, он устал и начал думать о следующей задаче.
Вам дана строка s. Сколько существует способов извлечь k ≥ 1 неперекрывающихся подстрок из неё, таких, что в каждой из них содержится t как подстрока? Более формально, требуется подсчитать количество способов выбора двух последовательностей, a1, a2, ..., ak и b1, b2, ..., bk, удовлетворяющих следующим требованиям:
- k ≥ 1
-
-
-
-
t является подстрокой строки saisai + 1... sbi (строка s индексируется с 1).
Так как количество способов может быть очень большим, выведите его по модулю 109 + 7.