DreamGrid 有一条包含 $n$ 个格子的纸带，他在其中一些格子里画了一些漂亮的图案。不幸的是，他那淘气的室友 BaoBao 在他不在家时，在另外一些格子里也画了一些图案。现在 DreamGrid 必须在不破坏自己图案的前提下，擦除 BaoBao 的图案。

我们将格子从左到右编号为 $1$ 到 $n$。每个格子要么包含 DreamGrid 的图案，要么包含 BaoBao 的图案，要么是空的。

每次，DreamGrid 可以选择两个整数 $l$ 和 $r$（每次选择的这两个整数可以不同），满足：

• $1 \le l \le r \le n$，且
• 对于所有 $l \le i \le r$，第 $i$ 个格子要么包含 BaoBao 的图案，要么是空的，

然后将所有 $l \le i \le r$ 的格子变为一个空格子。

请问 DreamGrid 通过恰好执行 $m$ 次上述操作，将所有包含 BaoBao 图案的格子变为空格子的方案数有多少种？由于答案可能很大，请输出答案对 $10^9 + 7$ 取模的结果。

设 $\{(a_1, b_1), (a_2, b_2), \dots, (a_m, b_m)\}$ 为一个合法的擦除序列（$1 \le a_i \le b_i \le n$），其中 $(a_i, b_i)$ 表示 DreamGrid 在第 $i$ 次操作中选择了整数 $a_i$ 和 $b_i$。设 $\{(c_1, d_1), (c_2, d_2), \dots, (c_m, d_m)\}$ 为另一个合法的擦除序列（$1 \le c_i \le d_i \le n$），其中 $(c_i, d_i)$ 表示 DreamGrid 在第 $i$ 次操作中选择了整数 $c_i$ 和 $d_i$。如果存在一个整数 $k$（$1 \le k \le m$）使得 $a_k \neq c_k$ 或 $b_k \neq d_k$，则这两个序列被视为不同。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100, 1 \le m \le 10^9$），表示格子的数量和执行操作的次数。

第二行包含 $n$ 个整数 $a_i$（$a_i \in \{0, 1, 2\}$）。

• 如果 $a_i = 0$，则第 $i$ 个格子为空。
• 如果 $a_i = 1$，则第 $i$ 个格子包含 DreamGrid 的图案。
• 如果 $a_i = 2$，则第 $i$ 个格子包含 BaoBao 的图案。

保证至多有 $50$ 组测试数据满足 $n > 50$。

输出格式

对于每组测试数据，输出一行，包含方案数对 $10^9 + 7$ 取模的结果。

样例

输入 1

3
2 2
2 0
3 2
2 1 0
3 1
2 1 0

输出 1

8
3
1