当前没有测试数据。

题目描述

小柯西截获了一长度为 n 的敌方密电。据了解，敌方密码一共由 m 种不同类型括号序列组成，且密码组成的规律是：

• 长度为 0的括号序列认为是一个合法的；
• 如果 A 是一个合法序列，x 是某种类型的左括号，y是同样类型的右括号，xAy 也是一种合法的密码括号序列；
• 如果 A,B都是合法的序列，那么 AB也是一个合法的序列。

输入格式

每个测试点包含多组测试数据。第一行为测试数据组数 T(1≤T≤20)。

每组测试数据格式为(每组测试数据占 2 行)：

第一行包含两个整数，n(1≤n≤500)为括号序列长度， m(1≤m<10^9+7)表示括号类型数（每种类型含左右两种括号）。

第二行包含n 个整数，a1,a2​,.....an*（ |ai​| ≤m），第 i 个整数ai表示序列中的第 i 个字符：

• 如果 ai=0，表示该位置的字符丢失了。
• 如果 ai>0，表示该位置是第 i 种左括号。
• 如果 ai<0，表示该位置是第 i 种右括号。 保证对于所有 n>100的测试点，最多有 15组测试数据。

输出格式

对于每组测试数据，输出一个整数，表示满足条件的括号序列个数（输出答案模 1000000007的值）。

对于部分情况，可能无法形成一个合法的括号序列（结果为 0）。

样例

3
4 2
1 0 0 -1
4 2
0 0 0 -1
6 3
0 0 0 0 0 0

3
4
135