E. Edge, Path, Number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fish has a directed graph and there is a label attached to each edge. A label is an integer ranging from $$$[0,9]$$$. If he chooses a vertex as start point, moves along $$$K$$$ edges in the graph, and writes down the labels in the edges walking through as $$$l_1,l_2,\cdots,l_K$$$, he can easily concatenate them to get a decimal integer $$$l=\overline{l_1l_2\cdots l_K}$$$.

Now he wonders, given $$$P$$$ and $$$X$$$, how many ways he can move so as to get a number $$$l$$$ satisfying $$$l \equiv X \pmod P$$$. Two ways are considered different if the order of edges walking through is different.

Input

The first line of input contains an integer $$$T$$$, representing the number of test cases.

Then for each test case:

The first line contains five integers $$$N, M, K, P, X$$$ as mentioned above, separated by one space .

Then $$$M$$$ lines follow, each line containing three integers $$$u, v, w$$$ which means that there exists an edge from node $$$u$$$ to node $$$v$$$ with label $$$w$$$.

Output

For each test case, you should output Case $$$x$$$: $$$y$$$, where $$$x$$$ indicates the case number starting from $$$1$$$ and $$$y$$$ is the number of ways.

Since $$$y$$$ can be very large, you should output $$$y \bmod (10^9+7)$$$ instead.

Example
Input
3
4 4 3 3 0
1 2 1
2 3 1
3 4 1
4 1 1
4 4 3 2 1
1 2 1
2 3 1
3 4 2
4 1 1
4 4 4 1111 0
1 2 1
2 3 1
3 4 1
4 1 1
Output
Case 1: 4
Case 2: 3
Case 3: 4
Note

$$$1\le T\le 100$$$

$$$1\le N\le 100$$$

$$$1\le M\le 1000$$$

$$$1\le K\le 8$$$

$$$1\le P \lt 10^K$$$

$$$0\le X \lt P$$$

For $$$90\%$$$ test cases: $$$N\le20$$$, $$$M\le100$$$, $$$K\le 6$$$