E. String Runs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The OF!Z language has $$$n$$$ words. However some words are too big for the database to store completely, so some are stored as the concatenation of other words in the database. Look at the input format for how a word is defined.

The desirability of a string $$$s$$$ is defined as $$$|f(s)|$$$ where $$$f(s)$$$ is the compression of all equal, adjacent characters into one character with same value as the compressed ones. For example, if $$$s = aabbbbaaaaccccaaaabaa$$$, then $$$f(s) = abacaba$$$ and the desirability of $$$s$$$ is $$$7$$$.

Everyone wants to know the desirability of the words, so for each word $$$w_i$$$, print its desirability modulo $$$10^9 + 7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 10^4)$$$. The description of each test case follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$ — the number of words in the language.

The next $$$n$$$ lines come in the following form:

$$$\cdot$$$ $$$1$$$ $$$s$$$ — this means that $$$w_i = s$$$. It is guaranteed that the first word is of this type.

$$$\cdot$$$ $$$2$$$ $$$k$$$ $$$x_1$$$ $$$x_2$$$ $$$\dots$$$ $$$x_k$$$ — this means that $$$w_i$$$ is the concatenation of strings with indices $$$x_1$$$ $$$x_2$$$ $$$\dots$$$ $$$x_k$$$ in that order. It is guaranteed that $$$1 \leq x_j \lt i$$$. It is not guaranteed that each $$$x_j$$$ is distinct.

It is guaranteed that all strings contain lowercase latin letters.

It is guaranteed that $$$\sum{|s|} \leq 2 \cdot 10^5$$$ across all queries of type $$$1$$$.

It is guaranteed that $$$\sum{k} \leq 2 \cdot 10^5$$$ across all queries of type $$$2$$$

Output

Print the desirability of each $$$w_i$$$ $$$(1 \leq i \leq n)$$$ modulo $$$10^9 + 7$$$, each separated by a space.

Example
Input
1
6
1 daniel
1 andrew
1 regina
1 yash
2 2 3 2
2 5 1 2 3 4 5
Output
6 6 6 4 11 33
Note

$$$s_4 = reginaandrew$$$ so its desirability is $$$11$$$.

$$$|f(s_5)| = 6 + 6 + 6 + 4 + 11 = 33$$$ so the desirability of $$$s_5$$$ is $$$33$$$.