{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDreamGrid has a paper strip with $n$ grids in a line and he has drawn some beautiful patterns in some grids. Unfortunately, his naughty roommate BaoBao drew some other patterns in some other grids when he wasn\u0027t at home. Now DreamGrid has to erase BaoBao\u0027s patterns without destroying his own patterns.\u003c/p\u003e\r\n\r\n\u003cp\u003eLet\u0027s number the grids from 1 to $n$ from left to right. Each grid either contains DreamGrid\u0027s pattern, or contains BaoBao\u0027s pattern, or is empty.\u003c/p\u003e\r\n\r\n\u003cp\u003eEach time, DreamGrid can select two integers $l$ and $r$ (these two integers can be different each time) such that\r\n\u003c/p\u003e\u003cul\u003e\r\n \u003cli\u003e$1 \\le l \\le r \\le n$, and\u003c/li\u003e\r\n \u003cli\u003efor all $l \\le i \\le r$, the $i$-th grid either contains BaoBao\u0027s pattern, or is empty,\u003c/li\u003e\r\n\u003c/ul\u003e\r\nand change the $i$-th grid to an empty grid for all $l \\le i \\le r$.\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003cp\u003eHow many ways can DreamGrid change all the grids containing BaoBao\u0027s pattern to empty grids by performing the above operation exactly $m$ times? As the answer may be large, please print the answer modulo $10^9 + 7$.\u003c/p\u003e\r\n\r\n\u003cp\u003eLet $\\{(a_1, b_1), (a_2, b_2), \\dots (a_m, b_m)\\}$ be a valid erasing sequence ($1 \\le a_i \\le b_i \\le n$), where $(a_i, b_i)$ indicates that DreamGrid selects integers $a_i$ and $b_i$ in the $i$-th operation. Let $\\{(c_1, d_1), (c_2, d_2), \\dots, (c_m, d_m)\\}$ be another valid erasing sequence ($1 \\le c_i \\le d_i \\le n$), where $(c_i, d_i)$ indicates that DreamGrid selects integers $c_i$ and $d_i$ in the $i$-th operation. These two sequences are considered different, if there exists an integer $k$ ($1 \\le k \\le m$) such that $a_k \\ne c_k$ or $b_k \\ne d_k$.\u003c/p\u003e\r\n\r\n\u003ch4\u003eInput\u003c/h4\u003e\r\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$ ($1 \\le T \\le 1000$), indicating the number of test cases. For each test case:\u003c/p\u003e\r\n\r\n\u003cp\u003eThe first line contains two integers $n$ and $m$ ($1 \\le n \\le 100$, $1 \\le m \\le 10^9$), indicating the number of grids and the number of times to perform the operation.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe second line contains $n$ integers $a_i$ ($a_i \\in \\{0, 1, 2\\}$).\r\n\u003c/p\u003e\u003cul\u003e\r\n \u003cli\u003eIf $a_i \u003d 0$, the $i$-th grid is empty.\u003c/li\u003e\r\n \u003cli\u003eIf $a_i \u003d 1$, the $i$-th grid contains DreamGrid\u0027s pattern.\u003c/li\u003e\r\n \u003cli\u003eIf $a_i \u003d 2$, the $i$-th grid contains BaoBao\u0027s pattern.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003cp\u003eIt\u0027s guaranteed that at most 50 test cases have $n \u0026gt; 50$.\u003c/p\u003e\r\n\r\n\u003ch4\u003eOutput\u003c/h4\u003e\r\n\u003cp\u003eFor each test case, output one line containing the number of ways modulo $10^9 + 7$.\u003c/p\u003e\r\n\r\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n2 2\r\n2 0\r\n3 2\r\n2 1 0\r\n3 1\r\n2 1 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\r\n3\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n"}}]}