The city of KOI is formed around a large river that flows from east to west. There are $N$ villages on the north side of the river and $N$ villages on the south side. The villages on the north side are identified as $A_1, A_2, \dots, A_N$ in order from downstream, and the villages on the south side are identified as $B_1, B_2, \dots, B_N$ in order from downstream. Thus, there are a total of $2N$ villages in the city of KOI.

Originally, the people of KOI traveled by raft, but with modernization, they began to build bridges across the river. Since the city of KOI developed from downstream, the first bridge built connected village $A_1$ and village $B_1$. The people of KOI call this first bridge the 0-th bridge. Subsequently, the city of KOI built the 1st bridge, 2nd bridge, $\dots$, $(2N-2)$-th bridge in order, for a total of $2N-1$ bridges.

After building the 0-th bridge, every subsequent bridge was built at a location adjacent to the one built immediately before it. Specifically, for all $0 \le i \le 2N-3$, if the $i$-th bridge connects village $A_x$ and village $B_y$, then the $(i+1)$-th bridge connects village $A_x$ and village $B_{y+1}$, or village $A_{x+1}$ and village $B_y$. Which of the two cases is chosen is recorded in a string $S$ of length $2N-2$. If $S[i] = \text{'A'}$, the $(i+1)$-th bridge connects village $A_x$ and village $B_{y+1}$, and if $S[i] = \text{'B'}$, the $(i+1)$-th bridge connects village $A_{x+1}$ and village $B_y$. $S$ contains exactly $N-1$ 'A's and $N-1$ 'B's. From this, it can be proven that the following facts hold:

• No bridge connects to a non-existent village.
• Any two distinct villages can always be reached from each other using only bridges.
• The $(2N-2)$-th bridge connects village $A_N$ and village $B_N$.

The city of KOI intends to carry out maintenance work on the bridges. The maintenance work is performed by selecting some of the $2N-1$ bridges. Because the work causes noise, they want to avoid having two or more bridges connected to the same village be subject to maintenance at the same time. The city of KOI wants to perform maintenance on as many bridges as possible while satisfying this condition. Furthermore, as unexpected problems may arise in the future, they wish to calculate the number of ways to perform maintenance on the maximum possible number of bridges, modulo $10^9 + 7$. Two maintenance plans are defined as different if the set of bridges subject to maintenance is different.

You must help the city of KOI calculate both of these values. However, you can also earn partial points by calculating only the maximum number of bridges.

Implementation Details

You must implement the following function:

array<int, 2> roadwork(string S)

• $S$: A string of size $2N-2$.
• This function can be called $T$ times in a single test case.
• If the maximum number of bridges that can undergo maintenance is $p$, and the number of ways to perform maintenance on $p$ bridges modulo $10^9 + 7$ is $q$, the function should return $[p, q]$. At this time, $0 \le q \le 10^9 + 6$ must be satisfied.

Do not execute any input/output functions in any part of your submitted source code.

Constraints

• $1 \le T \le 10$
• $2 \le N \le 2^{21}$
• $S$ contains exactly $N-1$ 'A's and $N-1$ 'B's.

Subtasks

1. (4 points) $N \le 2^1$
2. (5 points) $N \le 2^3$
3. (6 points) $N \le 2^5$
4. (7 points) $N \le 2^7$
5. (8 points) $N \le 2^9$
6. (9 points) $N \le 2^{11}$
7. (10 points) $N \le 2^{13}$
8. (11 points) $N \le 2^{15}$
9. (12 points) $N \le 2^{17}$
10. (13 points) $N \le 2^{19}$
11. (15 points) No additional constraints.

If you correctly return only the maximum number of bridges for each subtask, you will receive 40% of the partial points.

Examples

Example 1

Consider the case where $N = 2, S = \text{"AB"}$. The grader calls the function as follows:

roadwork("AB")

The figure below shows the structure of the city of KOI.

If you perform maintenance on the 0-th bridge and the 2nd bridge, you can perform maintenance on a maximum of 2 bridges. This is the only way to perform maintenance on 2 bridges. The function should return $[2, 1]$. If you return $[2, -1]$, $[2, 0]$, etc., it is considered that you have correctly returned only the maximum number of bridges.

There are 3 ways to perform maintenance on 1 bridge, but this case is not counted because it does not perform maintenance on the maximum possible number of bridges.

Example 2

Consider the case where $N = 7, S = \text{"AABBAABBAABB"}$. The grader calls the function as follows:

roadwork("AABBAABBAABB")

The figure below shows the structure of the city of KOI.

It is possible to perform maintenance on a maximum of 6 bridges. There are a total of 4 such ways. The function should return $[6, 4]$.