CF1729G Cut Substrings

给出两个非空字符串$s$和$t$，以最小次数删除使得字符串$s$中不会出现字符串$t$，每次可以将字符串$s$中所有任意一个字符串$t$删除，并且有多少种不同的的方案，如：删除序列$\{1,2,3\}$与删除序列$\{1,2,4\}$是不同的，删除序列$\{2,4,6\}$和删除序列$\{2,6\}$也是不同的，但删除序列$\{3,5\}$与删除序列$\{5,3\}$是相同的 现有$q$次询问，每次输出最小删除次数与以最小删除次数删除的方案数(对$10^9+7$取模)

第一行是询问次数$q(1\le q \le 50 )$，接下来一行字符串$s(1 \le |s| \le 500)$和一行字符串$t(1 \le |t| \le 500)$

$q$行答案，每次输出最小删除次数与以最小删除次数删除的方案数(对$10^9+7$取模)

第一个测试用例可以在第$3$个位置和第$9$位置删除，也可以在第$3$个位置和第$11$个位置删除，因此最优删除次数为$2$,有两种方案。 第二个测试用例下，只需要删除$4$个能够匹配的字符串任何一个就足够了 第三个测试用例下，字符串$s=\{xyzxyz\}$是两个字符串$t=\{xyz\}$的串联，因此存在 $2$ 个删除的唯一最优序列。 在第四个和第六个测试用例下，字符串 $s$ 不包含字符串 $t$ 。 在第五个测试用例下,字符串 $s$ 恰好为字符串 $t$ 。