F. Count via Construct
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This time Yugandhar came up with two binary strings $$$a$$$ and $$$b$$$ of length $$$n$$$ and is thinking of asking you to construct a binary matrix which has $$$n$$$ rows and $$$n$$$ columns, such that the following condition holds:

  1. Bitwise AND of all the numbers in the $$$i^{th}$$$ row of the constructed matrix will be equal to $$$a_{i}$$$ $$$(1 \le i \le n)$$$.
  2. Bitwise OR of all the numbers in the $$$i^{th}$$$ column of the constructed matrix will be equal to $$$b_{i}$$$ $$$(1 \le i \le n)$$$.

But Wuhudsm thinks it is boring to concentrate on a single thing. Hence, he asked you to calculate the number of different binary matrices of size $$$n$$$ rows and $$$n$$$ columns which you can construct to make the above conditions hold.

The number may be large so print it modulo $$$10^{9}+7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the length of binary strings $$$a$$$ and $$$b$$$.

The second line of each testcase contains a binary string $$$a$$$ of length $$$n$$$.

The third line of each testcase contains a binary string $$$b$$$ of length $$$n$$$.

Output

For each test case, print a single integer — the number of different binary matrices modulo $$$10^{9}+7$$$.

Example
Input
5
2
00
11
2
01
11
3
001
111
3
010
110
4
0000
0101
Output
2
3
49
0
225
Note

In the first test case, all possible matrices are:

01
10

10
01

In the second test case, all possible matrices are:

00
11

01
11

10
11