# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* notsoloud

*mridulahi*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1537

# PREREQUISITES:

Basic combinatorics

# PROBLEM:

Youβre given a binary string S of length N.

Find the number of *operation* strings o such that S_{2i-1} \ o_i \ S_{2i} = S_{2i+1} for every i.

Each o_i must belong to \{\oplus, \mid, \& \}, i.e, be one of bitwise XOR/OR/AND.

# EXPLANATION:

We know the string S already, which also includes the results of the operations.

So, elements of the *operation string* o are completely independent of each other: we can choose o_1, then o_2, then o_3, and so on separately; and multiply the choices for each of them.

This reduction simplifies the problem greatly, since we can deal with a single operation at a time.

That is, weβre given three bits b_1, b_2, b_3, and we want to count the number of bitwise operations op such that b_1 \ op \ b_2 = b_3.

With a bit of casework, this is not too hard:

- If b_3 = 1, then:
- If b_1 = b_2 = 0, then thereβs no way to achieve this; the answer is 0.
- If b_1 = 1 and b_2 = 0 (or vice versa), there are two choices: XOR and OR.
- If b_1 = b_2 = 1, there are again two choices: OR and AND.

- If b_3 = 0, then:
- If b_1 = b_2 = 0, then any of the three operations will work.
- If b_1 = 1 and b_2 = 0 (or vice versa), thereβs only one choice: AND
- If b_1 = b_2 = 1, thereβs again only one choice: XOR

So, depending on the values of b_1, b_2, b_3, the answer gets multiplied by one of \{0, 1, 2, 3\}.

Perform all these multiplications, and print the final result modulo 10^9 + 7.

This takes \mathcal{O}(N) time.

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (Python)

```
mod = 10**9 + 7
for _ in range(int(input())):
n = int(input())
s = input()
ans = 1
for i in range(0, n-1, 2):
result = s[i+2]
a, b = s[i], s[i+1]
if result == '1':
if a == '0' and b == '0': ans = 0
else: ans = ans * 2 % mod
else:
if a == '0' and b == '0': ans = ans * 3 % mod
print(ans)
```