小柯西截获了一长度为n的敌方密电。据了解,敌方密码一共由m种不同类型括号序列组成,且密码组成的规律是:
长度为0的括号序列认为是一个合法的;
如果A是一个合法序列,x是某种类型的左括号,y是同样类型的右括号,xAy也是一种合法的密码括号序列;
如果A,B都是合法的序列,那么AB也是一个合法的序列。
输入格式
每个测试点包含多组测试数据。第一行为测试数据组数T(1 ≤ T ≤ 20)。每组测试数据格式为(每组测试数据占2行):
第一行包含两个整数,n(1 ≤ n ≤ 500)为括号序列长度, m(1 ≤ m < 109 + 7)表示括号类型数(每种类型含左右两种括号)。
第二行包含n个整数,a1, a2, …… , an(|ai | ≤ m),第i个整数ai表示序列中的第i个字符:
· 如果 ai = 0, 表示该位置的字符丢失了。
· 如果ai > 0, 表示该位置是第i种左括号。
· 如果ai < 0, 表示该位置是第i种右括号。
输出格式
对于每组测试数据,输出一个整数,表示满足条件的括号序列个数(输出答案模1000000007的值)。
对于部分情况,可能无法形成一个合法的括号序列(结果为0)。
输入样例#1
3
4 2
1 0 0 -1
4 2
0 0 0 -1
6 3
0 0 0 0 0 0
输出样例#1
3
4
135