Вам даны две непустые строки \(s\) и \(t\), состоящие из латинских букв.
За один ход вы можете выбрать вхождение строки \(t\) в строку \(s\) и заменить его на точки.
Ваша задача — за минимальное количество ходов убрать все вхождения строки \(t\) в строке \(s\), а также посчитать, сколько существует различных последовательностей ходов минимальной длины.
Две последовательности ходов считаются различными, если множества индексов, в которых начинаются убираемые вхождения строки \(t\) в \(s\), различаются. Например, множества \(\{1, 2, 3\}\) и \(\{1, 2, 4\}\) считаются различными, множества \(\{2, 4, 6\}\) и \(\{2, 6\}\) — тоже, а множества \(\{3, 5\}\) и \(\{5, 3\}\) — нет.
Например, пусть строка \(s =\) «abababacababa», а строка \(t =\) «aba». Мы можем убрать все вхождения строки \(t\) за \(2\) хода, заменив вхождения строки \(t\) на \(3\)-й и \(9\)-й позициях на точки. В этом случае строка \(s\) пример вид «ab...bac...ba». Также можно вырезать вхождения строки \(t\) на \(3\)-й и \(11\)-й позициях. Всего есть две различные последовательности ходов минимальной длины.
Так как ответ может быть большим, выведите его по модулю \(10^9 + 7\).
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе достаточно заменить любое из четырёх вхождений.
В третьем наборе строка \(s\) является конкатенацией двух строк \(t =\) «xyz», поэтому существует единственная оптимальная последовательность из \(2\) ходов.
В четвёртом и шестом наборах строка \(s\) изначально не содержит вхождений строки \(t\).
В пятом наборе строка \(s\) содержит ровно одно вхождение строки \(t\).