Description

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$ 的第 $i$ 个格子变为空格子。

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 \ne c_k$ 或 $b_k \ne d_k$，则这两个序列被认为是不同的。

Input Format

有多个测试用例。输入的第一行包含一个整数 $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$。

Output Format

对于每个测试用例，输出一行，包含对 $10^9 + 7$ 取模的方式数量。

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

8
3
1

Hint

题面翻译由 ChatGPT-4o 提供。