Bridge Repair Optimization

A river flows from west to east. On its north bank there are n villages labeled A₁, A₂, \dots, A_n (from west to east), and on its south bank there are n villages labeled B₁, B₂, \dots, B_n (from west to east).

There are \(2n-1\) bridges. The bridges are built sequentially. They are uniquely determined by a string \(s\) of length \(2n-2\) with characters in \(\{A,B\}\) satisfying that exactly \(n-1\) characters are \(A\) and \(n-1\) are \(B\). The construction is as follows:

• The 0-th bridge connects villages \(A_1\) and \(B_1\).
• For each \(0 \le i < 2n-2\), suppose the \(i\)-th bridge connects \(A_x\) and \(B_y\). Then:
  • If \(s_i = A\), the \((i+1)\)-th bridge connects \(A_x\) and \(B_{y+1}\);
  • If \(s_i = B\), the \((i+1)\)-th bridge connects \(A_{x+1}\) and \(B_y\).

It can be verified that under these rules:

1. No bridge connects to a non-existent village;
2. Any two villages are connected through a sequence of bridges;
3. The last (\(2n-2\)-th) bridge connects \(A_n\) and \(B_n\).

Due to maintenance costs, only some bridges can be repaired. The repair work must satisfy that each village is incident to at most one repaired bridge (i.e. every village can be involved in at most one of the repaired bridges).

Your task is to compute:

1. The maximum number of bridges that can be repaired under the constraint.
2. Under that maximum, the number of different repair plans. (Two plans are different if the set of repaired bridges are different.) Report the second answer modulo \(10^9+7\).</p>

   You only need to implement the following function:

   array roadwork(string s);
   

   Here, s is a string of length \(2n-2\) (with exactly \(n-1\) occurrences of A and \(n-1\) occurrences of B). The returned array's first element is the maximum number of bridges that can be repaired, and the second element is the number of repair plans modulo \(10^9+7\).

   This function will be called for \(T\) test cases.

   inputFormat

   The input is a single string s as described above. Its length is \(2n-2\), where \(n\) is determined by \(n = (|s|+2)/2\). It is guaranteed that \(s\) contains exactly \(n-1\) characters 'A' and \(n-1\) characters 'B'.

   You do not need to implement input parsing; only implement the function roadwork as described.

   outputFormat

   The function should return an array of two integers. The first integer is the maximum number of bridges that can be repaired and the second is the number of different repair plans modulo 10^9+7.

   sample

   AB

   2 1