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

Вам дана строка s. Сколько существует способов извлечь k ≥ 1 неперекрывающихся подстрок из неё, таких, что в каждой из них содержится t как подстрока? Более формально, требуется подсчитать количество способов выбора двух последовательностей, a₁, a₂, ..., a_k и b₁, b₂, ..., b_k, удовлетворяющих следующим требованиям:

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

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