有一个包含 $n$ 个正整数的数组 $A$，以及 $m$ 个形如 $A[x] \text{ op } A[y] = z$ 的方程，其中 $x$ 和 $y$ 表示 $A$ 中的位置，$op \in \{+, -, *\}$，$z$ 是一个给定的整数，对于每个方程可能不同。 由于数组 $A$ 中的所有数字都缺失了，你需要找出这个数组并将它们打印出来。 如果存在多个不违反任何方程的数组，你只需要打印出有效数组的数量模 $(10^9 + 7)$ 的结果。

输入格式

输入文件的第一行包含一个整数 $T$ ($1 \le T \le 25$)，表示测试用例的数量。 对于每个测试用例，第一行包含两个整数 $n, m$ ($1 \le n \le 10^4, 1 \le m \le 10^6$)，随后是 $m$ 行。 接下来的 $m$ 行中，每一行包含一个形如 $xPy=z$ 的字符串，中间没有任何空格（$x, y, z$ 是数字，$P$ 是字符，$1 \le x, y \le n, P \in \{+, -, *\}, 0 \le z \le 10^6$），表示上述方程 $A[x] \text{ } P \text{ } A[y] = z$。 其中 $m \ge 10^5$ 的测试用例不超过 5 个。 你可能需要阅读样例输入以了解详细信息。

输出格式

你应该输出恰好 $T$ 行。 对于每个测试用例，首先打印 Case x: d（$x$ 表示测试用例的序号，$d$ 表示解的数量模 $(10^9 + 7)$，使用 $d = -1$ 表示无穷多解）。 如果数组是唯一的，则在 $d$ 之后输出 $n$ 个数字，描述该数组，数字之间用恰好一个空格分隔。 请注意，每个测试用例的结果仅占一行。

样例

输入 1

4
3 2
1+2=3
1*3=9
4 3
1+2=10
2+3=3
1+4=9
2 2
1+2=3
1-2=3
3 2
1+2=4
1*3=9

输出 1

Case 1: 1 1 2 9
Case 2: 1 8 2 1 1
Case 3: 0
Case 4: 2

说明

• 样例 1： 方程： – $A[1] + A[2] = 3$ – $A[1] \times A[3] = 9$ 只有唯一解：$A[1] = 1, A[2] = 2, A[3] = 9$。

• 样例 3： 方程： – $A[1] + A[2] = 3$ – $A[1] - A[2] = 3$ 数组 $A$ 无解。

• 样例 4： 方程： – $A[1] + A[2] = 4$ – $A[1] \times A[3] = 9$ 有两个解：$(A[1] = 1, A[2] = 3, A[3] = 9)$ 和 $(A[1] = 3, A[2] = 1, A[3] = 3)$。