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

Вам даны две непустые строки $$$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$$$.

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

Первая строка входных данных содержит единственное целое число $$$q$$$ ($$$1 \le q \le 50$$$) — количество наборов входных данных. Далее следуют описания наборов.

Первая строка каждого набора содержит непустую строку $$$s$$$ ($$$1 \le |s| \le 500$$$), состоящую из строчных латинских букв.

Вторая строка каждого набора содержит непустую строку $$$t$$$ ($$$1 \le |t| \le 500$$$), состоящую из строчных латинских букв.

Гарантируется, что сумма длин строк $$$s$$$ по всем наборам входных данных не превосходит $$$500$$$. Аналогично, гарантируется, что сумма длин строк $$$t$$$ по всем наборам входных данных не превосходит $$$500$$$.

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

Для каждого набора входных данных выведите два целых числа — минимальное количество ходов и количество различных оптимальных последовательностей, взятое по модулю $$$10^9 + 7$$$.

Пример
Входные данные
8
abababacababa
aba
ddddddd
dddd
xyzxyz
xyz
abc
abcd
abacaba
abaca
abc
def
aaaaaaaa
a
aaaaaaaa
aa
Выходные данные
2 2
1 4
2 1
0 1
1 1
0 1
8 1
3 6
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе достаточно заменить любое из четырёх вхождений.

В третьем наборе строка $$$s$$$ является конкатенацией двух строк $$$t =$$$ «xyz», поэтому существует единственная оптимальная последовательность из $$$2$$$ ходов.

В четвёртом и шестом наборах строка $$$s$$$ изначально не содержит вхождений строки $$$t$$$.

В пятом наборе строка $$$s$$$ содержит ровно одно вхождение строки $$$t$$$.