题目背景

版权信息：译自 2025年度 国际情报 올림피아드 (Olympiad) 代表学生 选拔考试 R1T3。[CC BY-NC-SA 4.0]

题目描述

有一条自西向东流的大河，河的南北两岸各有 $n$ 个村庄。北岸的村庄自西向东编号 $A_1\sim A_n$，南岸的村庄自西向东编号 $B_1\sim B_n$。

有 $(2n-1)$ 座桥梁，每座桥梁连接一个南岸村庄和北岸村庄。

具体地说，给定一个长为 $(2n-2)$ 的字符串 $s$，字符集为 $\{\texttt{A},\texttt{B}\}$。

• 第 $0$ 座桥连接 $A_1,B_1$；
• $\forall 0\le i\lt 2n-2$，设第 $i$ 座桥连接 $A_x,B_y$：
  • 若 $s_i=\texttt{A}$，则第 $(i+1)$ 座桥连接 $A_x,B_{y+1}$；
  • 若 $s_i=\texttt{B}$，则第 $(i+1)$ 座桥连接 $A_{x+1},B_{y}$。

数据保证，$s$ 中恰好有 $(n-1)$ 个 $\texttt{A}$ 和 $(n-1)$ 个 $\texttt{B}$，由此可以导出以下性质：

1. 不存在一条座桥梁，连接了不存在的村庄；
2. 任意两座村庄均通过桥梁连通；
3. 第 $(2n-2)$ 座桥（即最后一座桥）连接 $A_n,B_n$。

现在要维修若干座桥梁，前提是：

• 任意一座村庄至多只有一条桥梁被维修。

计算：

1. 在满足以上条件的前提下，至多能维修多少座桥梁。
2. 在满足 1 的前提下，有多少个不同的维修方案。

两个方案不同，当且仅当选择桥梁的集合不同。只需要将第二问的答案对 $(10^9+7)$ 取模。

特别地，如果你只回答第一问，也可以得到部分分，详见【计分方式】。

实现细节

你不需要，也不应该实现 main 函数。

你应当实现以下的函数：

array<int, 2> roadwork(string s);

• s：长度为 $(2n-2)$ 的字符串 $s$。
• 返回一个数组，第一个元素表示至多能维修多少座桥梁；第二个元素表示方案数对 $(10^9+7)$ 取模后的结果（落在区间 $[0,10^9+7)$ 内）。
• 该函数将被调用 $T$ 次，其中 $T$ 为测试数据组数。

输入格式

本题单个测试点内有多组测试数据。

Sample Grader 输入格式如下：

第一行，一个正整数 $T$。

接下来 $T$ 行，每行一个正整数 $n$ 和一个长度为 $(2n-2)$ 的字符串 $s$。

输出格式

Sample Grader 输出 $T$ 行，每行两个整数，表示对应数据的答案。

1
2 AB

2 1

1
7 AABBAABBAABB

6 4

提示

样例交互

样例交互 $1$

roadwork("AB");

显然至多能维修两座桥梁（$(A_1,B_1),(A_2,B_2)$），且这是唯一的方案。所以返回 $[2,1]$。

如果返回 $[2,-1],[2,0]$ 等，将得到 $40\%$ 的分数。

样例交互 $2$

roadwork("AABBAABBAABB")

至多维修 $6$ 座桥梁，有 $4$ 种方式。所以返回 $[6,4]$。

数据范围

• $1\le T\le 10$；
• $2^1\le n\le 2^{21}$；
• $s$ 中恰好有 $(n-1)$ 个 $\texttt{A}$ 和 $(n-1)$ 个 $\texttt{B}$。

子任务

子任务 $0$ 为样例。

子任务编号	$n\le$	得分
$1$	$2^{1}$	$4$
$2$	$2^{3}$	$5$
$3$	$2^{5}$	$6$
$4$	$2^{7}$	$7$
$5$	$2^{9}$	$8$
$6$	$2^{11}$	$9$
$7$	$2^{13}$	$10$
$8$	$2^{15}$	$11$
$9$	$2^{17}$	$12$
$10$	$2^{19}$	$13$
$11$	$2^{21}$	$15$

计分方式

如果你正确回答第一问，可以获得 $40\%$ 的分数。

在此前提下，如果你正确回答第二问，可以额外获得 $60\%$ 的分数。