解题思路
本题可以使用动态规划。
由于字符串只包含 A 和 B，我们从左到右处理字符串，维护当前最后一段字符的信息。
设：
- odd[c] 表示当前最后一段字符为 c，且这一段长度为奇数的方案数；
P4875.第2题-奇偶约束下的问号替换方案数
题目内容
给定一个长度为 n 的字符串 s，其中每个字符为 ′A′、′B′ 或 ′?′。你需要将每个 ′?′ 独立替换为 ′A′ 或 ′B′，得到最终字符串 t。
要求最终字符串 t 的每一段由相同字符组成的连续段（即相同字符的极大连续子串）长度均为奇数。请计算共有多少种不同的替换方案，答案对 109+7 取模。
输入描述
每个测试文件包含多组测试数据。第一行输入一个整数 T(1≤T≤105) 表示数据组数，每组测试数据描述如下：
- 第一行输入一个整数 n(1≤n≤2×105)，表示字符串长度。
- 第二行输入一个仅包含字符 ′A′、′B′、′?′ 的字符串 s，长度为 n。
保证所有测试数据的 n 之和不超过 2×105。
输出描述
对于每组测试数据，输出一个整数，表示满足要求的替换方案数，结果对 109+7 取模。
样例1
输入
2
2
??
5
A?B??
输出
2
1
说明
示例1 说明
合法只有 AB、BA 两种，两段长度都是 1（奇数），共2 种方案。
- 第二组：n=5，字符串 A?B??
只有一种替换方式能让每段相同字符连续长度都为奇数，故输出 1。
