November 30, 2023
Latest:
CodeChef Solution

# Bit Play CodeChef Solution ## Problem

Chefina has a binary string  of odd length .
She also has an operation string  of length (�−1)2 where ��∈{&,∣,⊕}. Note that &,∣,⊕ denote the bitwise andor, and xor operations respectively.

The following conditions are satisfied with respect to the strings:

• �3=�1 �1 �2;
• �5=�3 �2 �4;
• �7=�5 �3 �6;

• ��=��−2 �(�−1)2 ��−1.

Help Chef find the number of operation strings  which satisfy the conditions. Since the number can be huge, print it modulo 109+7.

### Input Format

• The first line of input will contain a single integer , denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains an odd integer  — the length of the string.
• The next line consists of a binary string  of length .

### Output Format

For each test case, output on a new line, the number of operation strings  which satisfy the conditions, modulo 109+7.

### Constraints

• 1≤�≤3000
• 3≤�≤105+1 is odd.
• ��∈{0,1}
• ��∈{&,∣,⊕}.
• The sum of  over all test cases won’t exceed 2⋅106.

### Sample 1:

Input

Output

3
3
110
5
00110
5
10101

1
0
4


### Explanation:

Test case 1: The only operation string  that satisfies the conditions is �=⊕.
Here, �3=�1�1�2=1⊕1=0.

Test case 2: There is no operation string that satisfies the given conditions.

Test case 3: The operation strings that satisfy the given conditions are:

• �=⊕⊕�3=�1 �1 �2=1⊕0=1�5=�3 �2 �4=1⊕0=1.
• �=⊕∣�3=�1 �1 �2=1⊕0=1�5=�3 �2 �4=1∣0=1.
• �=∣⊕�3=�1 �1 �2=1∣0=1�5=�3 �2 �4=1⊕0=1.
• �=∣∣�3=�1 �1 �2=1∣0=1�5=�3 �2 �4=1∣0=1. 