题目描述

点击查看pdf

Let $f(x)$ denote the number of 1s in the binary representation of $x$.

Now MianKing has a sequence $a_{0...m-1}$ and he wants to know the number of integer $x \\in [0,L]$ satisfies that: $\\forall i\\in [0,m-1], f(x+i)~mod~2=a_i$

You need to help him calculate the answer.

输入格式

There are $T$ testcases in this problem.

The first line has one integer $T$.

Then for each testcase, the first line has two integer $m,L$. The second line has $m$ integers denote $a_{0...m-1}$

$1\\leq T\\leq 1000$

$1\\leq m\\leq 100$

$0\\leq L\\leq 10^{18}$

$a_i \\in \\{0,1\\}$

输出格式

For each testcase, output the answer in one line.

样例

3 
3 10 
0 1 0 
1 1000 
0 
9 1000000 
1 0 1 1 0 1 0 0 1 

2 
501 
41667 

提示

Form 2020ICPC济南站