H. You delete matrices I delete memories
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

When Ahmad found out about Ammar's evil plan, he got mad and decided to take revenge. He asked his wizard friend Mousa (yes, everyone has a wizard friend) to help him.

Mousa threw Ammar in a DAG (directed acyclic graph) of $$$n$$$ nodes and $$$m$$$ edges, where each edge has a lowercase letter on it , and to escape he has to find the password. The password is a string $$$s$$$ of length $$$k$$$ , consisting of lowercase letters. Ammar starts in node $$$1$$$ and will choose a path to take in the graph. His memory can be represented as a string $$$t$$$, initially empty. When he walks on an edge, he adds the letter on the edge to the end of $$$t$$$. But Mousa cast the forgetting spell on Ammar, so when his memory becomes equal to the password, it becomes empty again.

Ammar's memory has to be equal to a prefix (possibly empty) of the password when he finishes walking to be able to escape the DAG.

Ammar wonders how many paths of length at least $$$1$$$ in the graph he can choose so that he escapes the DAG in the end? Since the answer might be very large, print it modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$— the number of testcases.

The first line of each testcase consists of $$$3$$$ integers $$$n,m,k \: (2 \leq n \leq 10^5)(1 \leq m \leq 2*10^5)(1 \leq k \leq 100)$$$ —the number of nodes, the number of edges and the length of the password and when Ammar forgets everything again.

The second line of each test case contains the string $$$s$$$ of length $$$k$$$ containing only lowercase latin letters.

Each of the next $$$m$$$ lines consists of $$$2$$$ integers $$$u,v \: (1 \leq u,v \leq n) (u\not=v)$$$ and a lowercase latin letter $$$c$$$ — this means there is an edge from $$$u$$$ to $$$v$$$ with the letter $$$c$$$ on it.

Multiple edges with the same character can exist.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$10^5$$$.

It is guaranteed that the sum of $$$m$$$ over all testcases doesn't exceed $$$2*10^5$$$.

It is guaranteed that the sum of $$$k$$$ over all testcases doesn't exceed $$$100$$$.

Output

For each testcase, print the number of paths Ammar can choose in order to escape the DAG, modulo $$$10^9 + 7$$$.

Example
Input
1
5 10 3
cca
3 4 c
2 3 c
3 4 a
1 2 c
1 2 b
3 4 b
2 3 b
4 5 c
4 5 a
1 2 a
Output
4