CF1729G Cut Substrings

给出两个字符串 $s$ 和 $t$，由小写字母组成。 在一次操作中，你可以选择 $s$ 中的一个 $t$，并将其替换为点号。 你的任务是使用最少的操作次数让 $s$ 中不会出现 $t$，并计算以最小操作次数让 $s$ 中不会出现 $t$ 的方案数。 两种方案被视为不同，当且仅当它们替换的 $t$ 在 $s$ 中的起始位置集合不同。例如，集合 $\{1,2,3\}$ 和 $\{1,2,4\}$ 被认为是不同的；$\{2,4,6\}$ 和 $\{2,6\}$ 也不同；但 $\{3,5\}$ 和 $\{5,3\}$ 是相同的。 例如，$s=\texttt{abababacababa},t=\texttt{aba}$。我们可以通过在第 $3$ 个位置和第 $9$ 个位置将 $t$ 替换，在 $2$ 次操作内让 $s$ 中不会出现 $t$。此时字符串 $s$ 变为 $\texttt{ab...bac...ba}$。也可以在第 $3$ 个和第 $11$ 个位置将 $t$ 替换。因此有 $2$ 种不同的最短操作序列。 由于答案可能很大，输出结果请对 $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$ 取模）。

第一个样例已在题目描述中解释。 第二个样例中，替换掉四个 $t$ 中的任意一个即可。 第三个样例中，$s$ 是两个 $t=\texttt{xyz}$ 的拼接，因此有唯一的最优操作序列（$2$ 次操作）。 第四个和第六个样例中，$s$ 初始不包含 $t$。 第五个样例中，$s$ 恰好包含一个 $t$。