Cut Substrings
Contest: Codeforces Round 820 (Div. 3)
Difficulty rating: 2100
Tags: combinatorics, dp, hashing, strings, two pointers

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$$$.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

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

Example output:
2 2
1 4
2 1
0 1
1 1
0 1
8 1
3 6

Editorial:
First, find all occurrences of $$$t$$$ in $$$s$$$ as substrings. This can be done using the prefix function.
To find the minimum number of times we need to cut substrings, consider all indexes of occurrences. Having considered the index of the occurrence, we cut out the rightmost occurrence that intersects with it. After that, we find the leftmost occurrence that does not intersect with the cut one. If it doesn't, we end the loop.
The number of optimal sequences of moves will be calculated using dynamic programming.
For each occurrence, we can count how many ways we can cut out all occurrences of $$$t$$$ in the suffix $$$s$$$ starting with this occurrence in the minimum number of moves. Considering the occurrence, we find the leftmost occurrence that does not intersect with it, and then iterate over the occurrences with which we can remove it.