Fish 有一个有向图，每条边上都有一个标签。标签是一个范围在 $[0, 9]$ 之间的整数。如果他选择一个顶点作为起点，在图中沿边移动 $K$ 次，并将沿途经过的边的标签记为 $l_1, l_2, \dots, l_K$，他可以很容易地将它们连接起来得到一个十进制整数 $l = l_1l_2 \dots l_K$。

现在他想知道，给定 $P$ 和 $X$，有多少种移动方式可以使得得到的数字 $l$ 满足 $l \equiv X \pmod P$。如果经过边的顺序不同，则视为不同的移动方式。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例： 第一行包含五个整数 $N, M, K, P, X$，含义如上所述，用空格分隔。 接下来 $M$ 行，每行包含三个整数 $u, v, w$，表示存在一条从节点 $u$ 到节点 $v$ 且标签为 $w$ 的边。

输出格式

对于每个测试用例，输出 Case x: y，其中 $x$ 表示从 1 开始的用例编号，$y$ 是方案数。 由于 $y$ 可能非常大，请输出 $y \pmod{10^9 + 7}$。

样例

样例输入 1

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

样例输出 1

Case 1: 4
Case 2: 3
Case 3: 4

数据范围

$1 \le T \le 100$ $1 \le N \le 100$ $1 \le M \le 1000$ $1 \le K \le 8$ $1 \le P < 10^K$ $0 \le X < P$ 对于 90% 的测试用例：$N \le 20, M \le 100, K \le 6$