CF1729G.Cut Substrings

You are given two non-empty strings $s$ and $t$, consisting of Latin letters.

In one move, you can choose an occurrence of the string $t$ in the string $s$ and replace it with dots.

Your task is to remove all occurrences of the string $t$ in the string $s$ in the minimum number of moves, and also calculate how many different sequences of moves of the minimum length exist.

Two sequences of moves are considered different if the sets of indices at which the removed occurrences of the string $t$ in $s$ begin differ. For example, the sets ${1, 2, 3}$ and ${1, 2, 4}$ are considered different, the sets ${2, 4, 6}$ and ${2, 6}$ — too, but sets ${3, 5}$ and ${5, 3}$ — not.

For example, let the string $s =$ "abababacababa" and the string $t =$ "aba". We can remove all occurrences of the string $t$ in $2$ moves by cutting out the occurrences of the string $t$ at the $3$th and $9$th positions. In this case, the string $s$ is an example of the form "ab...bac...ba". It is also possible to cut occurrences of the string $t$ at the $3$th and $11$th positions. There are two different sequences of minimum length moves.

Since the answer can be large, output it modulo $10^9 + 7$.

给你两个非空字符串 $s$ 和 $t$，均由拉丁字母组成。

在一次操作中，你可以选择字符串 $s$ 中一个 $t$ 的出现位置，并将其替换为若干个点号（.）。

你的任务是以最少的操作次数移除字符串 $s$ 中所有 $t$ 的出现，并计算有多少种不同的、长度为最小值的操作序列。

若两个操作序列所移除的 $t$ 在 $s$ 中起始位置的集合不同，则认为这两个序列不同。例如，集合 $\{1, 2, 3\}$ 和 $\{1, 2, 4\}$ 被视为不同；集合 $\{2, 4, 6\}$ 和 $\{2, 6\}$ 也视为不同；但集合 $\{3, 5\}$ 和 $\{5, 3\}$ 不视为不同（集合无序）。

例如，设字符串 $s =$ "abababacababa"，字符串 $t =$ "aba"。我们可以通过 2 次操作移除所有 $t$ 的出现：例如移除起始位置为第 $3$ 位和第 $9$ 位的两个 "aba"。此时 $s$ 变为形如 "ab...bac...ba" 的字符串。同样地，也可选择移除起始位置为第 $3$ 位和第 $11$ 位的两个 "aba"。因此，共有两种不同的、长度最小的操作序列。

由于答案可能很大，请将结果对 $10^9 + 7$ 取模后输出。

The first line of the input contains a single integer $q$ ($1 \le q \le 50$) — the number of test cases. The descriptions of the sets follow.

The first line of each set contains a non-empty string $s$ ($1 \le |s| \le 500$) consisting of lowercase Latin letters.

The second line of each set contains a non-empty string $t$ ($1 \le |t| \le 500$) consisting of lowercase Latin letters.

It is guaranteed that the sum of string lengths $s$ over all test cases does not exceed $500$. Similarly, it is guaranteed that the sum of string lengths $t$ over all test cases does not exceed $500$.

输入的第一行包含一个整数 $q$（$1 \le q \le 50$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个非空字符串 $s$（$1 \le |s| \le 500$），由小写拉丁字母组成。

每个测试用例的第二行包含一个非空字符串 $t$（$1 \le |t| \le 500$），由小写拉丁字母组成。

保证所有测试用例中字符串 $s$ 的长度总和不超过 $500$；同样，保证所有测试用例中字符串 $t$ 的长度总和不超过 $500$。

For each test case print two integers — the minimum number of moves and the number of different optimal sequences, modulo $10^9 + 7$.

对于每个测试用例，输出两个整数——最小移动次数以及不同最优序列的数量（对 $10^9 + 7$ 取模）。

The first test case is explained in the statement.

In the second case, it is enough to cut any of the four occurrences.

In the third case, string $s$ is the concatenation of two strings $t =$ "xyz", so there is a unique optimal sequence of $2$ moves.

In the fourth and sixth cases, the string $s$ initially contains no occurrences of the string $t$.

In the fifth case, the string $s$ contains exactly one occurrence of the string $t$.

第一个测试用例已在题目描述中说明。

在第二个测试用例中，只需剪切四个出现位置中的任意一个即可。

在第三个测试用例中，字符串 $s$ 是两个字符串 $t =$ "xyz" 的连接，因此存在唯一最优的操作序列，共需 $2$ 步。

在第四个和第六个测试用例中，字符串 $s$ 初始时不包含字符串 $t$ 的任何出现。

在第五个测试用例中，字符串 $s$ 恰好包含字符串 $t$ 的一个出现。