切除子串

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定两个小写字母串 $s,t$。一次操作选择 $s$ 中一次出现的 $t$，并把对应字符全部替换为点号。求使 $s$ 中不再出现 $t$ 的最少操作次数，以及达到最少次数的不同选择集合数量。方案只由被选择的起始位置集合决定，答案对 $10^9+7$ 取模。

输入格式

第一行包含测试组数 $q$。每组依次给出字符串 $s$ 和 $t$，各占一行。

输出格式

每组输出两个整数：最少操作次数和方案数。

样例输入 1

8
abababacababa
aba
ddddddd
dddd
xyzxyz
xyz
abc
abcd
abacaba
abaca
abc
def
aaaaaaaa
a
aaaaaaaa
aa

样例输出 1

2 2
1 4
2 1
0 1
1 1
0 1
8 1
3 6

数据范围

• $1\le q\le50$；
• $1\le |s|,|t|\le500$；
• 每个输入文件中所有 $|s|$ 之和、所有 $|t|$ 之和分别不超过 $500$。