You are given a string of length , containing characters W and characters B.
Let's build a graph on nodes. If s_i \neq s_j for some 1 \le i < j \le 2n, then there is an edge of weight |i-j| between nodes and in this graph. There are no other edges.
Find the number of shortest Hamiltonian cycles in this graph. As this number can be very large, output it modulo .
As a reminder, a Hamiltonian cycle is a cycle that visits each node exactly once. The length of the cycle is equal to the sum of the weights of its edges. Two cycles are called different if there is an edge that one contains and the other doesn't.
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer (2 \le n \le 10^6).
The second line of each test case contains a string of length , containing characters W and characters B.
It is guaranteed that the sum of over all test cases does not exceed 10^6.
For each test case, output the number of shortest Hamiltonian cycles in this graph, modulo .
Example 1
In the first test case, the graph has edges: with weight , with weight , with weight , and with weight .
There is only one Hamiltonian cycle here: 1 \to 3 \to 2 \to 4 \to 1 (Note that, for example, cycle 1 \to 4 \to 2 \to 3 contains the same set of edges, so we have already counted it).