KOI 市以一条东西横贯城市的河流为中心。河流的北岸和南岸各有 $N$ 个村庄。北岸的村庄从下游起依次标识为 $A_1, A_2, \dots, A_N$，南岸的村庄从下游起依次标识为 $B_1, B_2, \dots, B_N$。因此，KOI 市共有 $2N$ 个村庄。
KOI 市的居民最初通过木筏往来交流，但随着现代化的推进，开始建设横跨河流的桥梁。由于 KOI 市是从下游开始发展的，最早建设的桥梁连接了村庄 $A_1$ 和村庄 $B_1$。KOI 市的居民将这座最早建设的桥称为 0 号桥。此后，KOI 市又依次建设了 1 号桥、2 号桥、$\dots$、$2N-2$ 号桥，总共建设了 $2N-1$ 座桥。
在建设 0 号桥之后，每一座桥都建设在紧邻上一座桥的位置。具体来说，对于所有 $0 \le i \le 2N-3$，如果 $i$ 号桥连接的是村庄 $A_x$ 和村庄 $B_y$，那么 $i+1$ 号桥要么连接村庄 $A_x$ 和村庄 $B_{y+1}$，要么连接村庄 $A_{x+1}$ 和村庄 $B_y$。这两种情况由长度为 $2N-2$ 的字符串 $S$ 记录。如果 $S[i] = \text{'A'}$，则 $i+1$ 号桥连接村庄 $A_x$ 和村庄 $B_{y+1}$；如果 $S[i] = \text{'B'}$，则 $i+1$ 号桥连接村庄 $A_{x+1}$ 和村庄 $B_y$。$S$ 中恰好包含 $N-1$ 个 $\text{'A'}$ 和 $N-1$ 个 $\text{'B'}$。由此可以证明以下事实成立：
- 不存在连接不存在的村庄的桥。
- 任意两个不同的村庄总是可以通过桥梁相互到达。
- $2N-2$ 号桥连接村庄 $A_N$ 和村庄 $B_N$。
KOI 市计划对桥梁进行维修工程。维修工程从 $2N-1$ 座桥中选择若干座进行。由于施工会产生噪音，因此要避免任何一个村庄同时连接两座或两座以上正在施工的桥。KOI 市希望在满足该条件的前提下，尽可能多地对桥梁进行维修。此外，考虑到未来可能出现意想不到的问题，还需要计算在满足条件的前提下，能够进行维修的桥梁数量达到最大值的情况数，结果对 $10^9+7$ 取模。两种施工方案不同，定义为施工的桥梁集合不同。
你需要帮助 KOI 市计算这两个值。即使只计算出桥梁的最大数量，也可以获得部分分数。
实现细节
你需要实现以下函数：
array<int, 2> roadwork(string S)- $S$: 长度为 $2N-2$ 的字符串。
- 该函数在单个测试用例中可被调用 $T$ 次。
- 若维修工程中可维修的桥梁最大数量为 $p$，且维修 $p$ 座桥的情况数对 $10^9+7$ 取模的结果为 $q$，则函数应返回 $[p, q]$。此时需满足 $0 \le q \le 10^9+6$。
提交的源代码中不得执行任何输入输出函数。
数据范围
- $1 \le T \le 10$
- $2 \le N \le 2^{21}$
- $S$ 中恰好包含 $N-1$ 个 $\text{'A'}$ 和 $N-1$ 个 $\text{'B'}$。
子任务
- (4分) $N \le 2^1$
- (5分) $N \le 2^3$
- (6分) $N \le 2^5$
- (7分) $N \le 2^7$
- (8分) $N \le 2^9$
- (9分) $N \le 2^{11}$
- (10分) $N \le 2^{13}$
- (11分) $N \le 2^{15}$
- (12分) $N \le 2^{17}$
- (13分) $N \le 2^{19}$
- (15分) 无额外限制。
在每个子任务中，如果仅正确返回了桥梁的最大数量，可获得 40% 的部分分数。
样例
样例 1
考虑 $N=2, S=\text{"AB"}$ 的情况。评测机调用函数如下：
roadwork("AB")下图展示了 KOI 市的结构：
如果对 0 号桥和 2 号桥进行维修，最多可以维修 2 座桥。这是维修 2 座桥的唯一方法。函数应返回 $[2, 1]$。如果返回 $[2, -1], [2, 0]$ 等，则视为仅正确返回了桥梁的最大数量。
虽然有 3 种维修 1 座桥的方法，但由于这种情况不是维修尽可能多的桥，因此不计入。
样例 2
考虑 $N=7, S=\text{"AABBAABBAABB"}$ 的情况。评测机调用函数如下：
roadwork("AABBAABBAABB")下图展示了 KOI 市的结构：
最多可以维修 6 座桥。这种情况共有 4 种。函数应返回 $[6, 4]$。
Sample grader
Sample grader 按以下格式接收输入：
- 第 1 行: $T$
- 第 $2+i$ 行 ($0 \le i \le T-1$): $N \ S$
设第 $i+1$ 个测试用例中 roadwork 返回的数组为 $C[i]$。Sample grader 输出：
- 第 $1+j$ 行 ($0 \le j \le T-1$): $C[j][0] \ C[j][1]$
请注意，Sample grader 可能与实际评测时使用的评测机不同。