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_1 l_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.
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$.
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.
$1 <= T <= 100$
$1 <= N <= 100$
$1 <= M <= 1000$
$1 <= K <= 8$
$1 <= P < 10^K$
$0 <= X < P$
For $90 %$ test cases: $N <= 20$, $M <= 100$, $K <= 6$
## 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.
[samples]
## Note
$1 <= T <= 100$$1 <= N <= 100$$1 <= M <= 1000$$1 <= K <= 8$$1 <= P < 10^K$$0 <= X < P$For $90 %$ test cases: $N <= 20$, $M <= 100$, $K <= 6$
**Definitions**
Let $ t \in \mathbb{Z}^+ $ be the number of taco types.
Let $ e \in \mathbb{Z}_{\geq 0} $ be the number of exchange operations.
Let $ c_i \in \mathbb{Z}^+ $ for $ i \in \{0, \dots, t-1\} $ be the base price of taco type $ i $.
Let $ d_i \in \mathbb{Z}^+ $ for $ i \in \{0, \dots, t-1\} $ be the desired count of taco type $ i $.
Let $ G = (V, E) $ be a directed graph where $ V = \{0, \dots, t-1\} $, and for each exchange $ (i, j, p) $, there is a directed edge $ i \to j $ with weight $ p $.
**Constraints**
1. $ 1 \leq t \leq 10^4 $
2. $ 0 \leq e \leq 10^5 $
3. $ 1 \leq c_i \leq 10^4 $ for all $ i $
4. $ 1 \leq d_i \leq 10^4 $ for all $ i $
5. $ 0 \leq p_{i,j} \leq 10^4 $ for all exchanges
**Objective**
Compute the minimum total cost to acquire $ d_i $ units of each taco type $ i $, starting from zero, where:
- You may buy taco $ i $ directly at cost $ c_i $, or
- Exchange taco $ j $ for taco $ i $ at cost $ p_{j,i} $, with unlimited exchanges.
Define $ \ell_i $ as the minimum cost to obtain one unit of taco type $ i $, considering direct purchase and any sequence of exchanges:
$$
\ell_i = \min\left( c_i,\ \min_{\text{paths } j_0 \to j_1 \to \dots \to j_k = i} \left( c_{j_0} + \sum_{m=0}^{k-1} p_{j_m, j_{m+1}} \right) \right)
$$
Then the total minimum cost is:
$$
\sum_{i=0}^{t-1} d_i \cdot \ell_i
$$