题目内容

在一种古老的珠宝镶嵌工艺中，工匠需要设计一条由 $m$ 颗宝石串成的手链。每颗宝石的颜色用一个英文小写字母表示（\texttt{a} 到 \texttt{z}）。工艺要求相邻两颗宝石的颜色必须不同。

工匠拿到了一份设计草图，草图上有些位置已经指定了颜色（即一个小写字母），有些位置标为 exttt{?} 表示尚未指定，可以由工匠自由选择颜色。

请你计算：在所有完全遵循草图（非 exttt{?} 位必须使用对应颜色， exttt{?} 位可任意选择）且满足相邻颜色不同的方案中，一共有多少种可能的手链颜色序列？

由于答案可能很大，需要对 $10^9+7$ 取模后输出。

整数 $T$ 满足 $1 \le T \le 1000$。每组字符串长度 $m$ 满足 $1 \le m \le 10^5$，且所有 $m$ 之和不超过 $5 \times 10^5$。

输入描述

第一行包含一个整数 $T$，表示数据组数。 接下来依次描述每组数据：

每组数据第一行包含一个整数 $m$，表示序列长度。 第二行包含一个长度为 $m$ 的字符串，仅由小写字母和字符 exttt{?} 构成，表示草图上的颜色标记。

输出描述

对于每组数据，输出一行一个整数，表示满足条件的颜色序列数量对 $10^9+7$ 取模的结果。

样例1

输入

1
1
?

输出

26

说明

当手链只有 1 颗宝石时，不存在相邻位置，因此任何字母都满足要求。 草图 ? 表示可以自由选择 a 到 z 中的任意一个小写字母，共有 $26$ 种方案。 所以答案为 $26$。

样例2

输入

2
3
???
3
abb

输出

16250
0

说明

第一组数据 ???，长度为 3：

• 第 1 位可以任选 $26$ 种字母；
• 第 2 位不能与第 1 位相同，有 $25$ 种选择；
• 第 3 位不能与第 2 位相同，也有 $25$ 种选择。 总方案数为 $26 \times 25 \times 25 = 16250$。

第二组数据 abb，长度为 3： 第 2 位与第 3 位固定为 b 和 b，它们是相邻位置且颜色相同，违反了工艺中相邻颜色不同的要求。 因此不存在合法方案，答案为 0。

样例3

输入

2
4
a??a
3
a?a

输出

600
25

说明

第一组数据 a??a，长度为 4，首尾固定为 a：

• 第 1 位固定为 a，只有 $1$ 种；
• 第 2 位是 ?，不能是 a，有 $25$ 种可选字母；
• 第 3 位是 ?，不能与第 2 位相同，也不能与第 4 位的 a 相同。由于第 2 位已经不能是 a，因此第 3 位需要排除 $2$ 个不同的字母，剩余 $24$ 种选择；
• 第 4 位固定为 a，前述约束已保证满足。 总方案数为 $1 \times 25 \times 24 = 600$。

第二组数据 a?a，长度为 3，首尾固定为 a：

• 第 1 位固定为 a；
• 第 2 位是 ?，不能是 a，有 $25$ 种选择；
• 第 3 位固定为 a，只需与第 2 位不同。因为第 2 位已不是 a，所有 $25$ 种选择都满足要求。 总方案数为 $25$。