在有向图上，我们用 $lex(p)$ 表示路径 $p$ 的词法权重，其中路径 $p$ 可以看作是一系列连续边的序列。词法权重由以下递推关系定义：

$$lex([]) = 0, lex([e_1, e_2, \dots, e_n]) = \frac{w(e_1) + lex([e_2, e_3, \dots, e_n])}{10}$$

其中 $w(e_1)$ 是边 $e_1$ 的权重，为一个 $0$ 到 $9$ 之间的整数（包含 $0$ 和 $9$）。

给定一个有向图，求从节点 $0$ 到节点 $1$ 的所有路径的词法权重的下确界。实数集合的下确界是指如果存在，则小于或等于该集合中所有元素的最大实数。

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 100$)。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含两个整数 $n$ ($2 \le n \le 2000$, $\sum n \le 20000$) 和 $m$ ($1 \le m \le 4000$, $\sum m \le 40000$)，其中 $n$ 是节点数，$m$ 是边数。

接下来 $m$ 行，每行包含三个整数 $u, v, w$ ($0 \le u, v < n, 0 \le w \le 9$)，表示一条从 $u$ 到 $v$ 权重为 $w$ 的边。

保证对于每个测试用例，至少存在一条从节点 $0$ 到节点 $1$ 的路径。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是答案对 $(10^9 + 7)$ 取模的结果。更具体地说，如果答案可以表示为不可约分数 $\frac{A}{B}$，则 $y$ 为 $(A \cdot B^{-1}) \pmod{10^9 + 7}$。

样例

输入 1

2
5 5
0 2 3
2 3 4
2 4 1
3 1 2
4 1 3
5 6
0 1 9
2 0 6
3 0 1
0 3 3
4 0 3
4 2 7

输出 1

Case #1: 241000002
Case #2: 40404041

说明

对于第一个样例，对应下确界的路径是 $0 \to 2 \to 4 \to 1$，因此答案是 $0.313$。