题目内容

在一次信息传输中，原始信息是由小写字母组成的字符串，且传输协议严格规定：相邻的两个字符不能相同。

由于信道存在严重干扰，恰有一种字母在传输过程中被完全丢失，最终接收方只看到了一个残存的字符串 $s$。已知 $s$ 仅由小写字母构成，且恰好等于原始信息删去全部丢失字母后得到的结果。

对于每一种可能丢失的字母，请你计算有多少个不同的合法原始信息，在移除该字母的所有出现后会得到 $s$。最终，将全部 $26$ 种可能丢失字母所对应的合法原始信息数量求和，并输出该和对 $10^9+7$ 取模的结果。

数据范围：测试用例组数不超过 $10^5$，每组中字符串的长度不超过 $2 \times 10^5$，所有字符串的总长度不超过 $5 \times 10^5$。所有字符串仅含小写字母。

输入描述

第一行包含一个整数 $q$（$1 \le q \le 10^5$），表示测试数据的组数。 接下来有 $q$ 组数据，每组两行：

• 第一行包含一个整数 $m$（$1 \le m \le 2 \times 10^5$），表示字符串的长度。
• 第二行包含一个长度为 $m$、仅由小写字母构成的字符串 $s$。 保证所有测试用例的 $m$ 之和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示所有可能丢失字母对应的合法原始信息数量之和对 $10^9+7$ 取模的结果。

样例1

输入

1
1
z

输出

100

说明

字符串长度为 1，仅包含字母 z，因此出现的字母种类数 $kind=1$。

字符串没有相邻字符对，故相邻不同位置的数量 $diff=0$。

未出现在 $s$ 中的字母共有 $26-1=25$ 种，即 $miss=25$。

对每一种未出现的字母 $c$，合法的原始信息有 $2^{diff+2}=2^{2}=4$ 种。

总和为 $25 \\times 4 = 100$，对 $10^9+7$ 取模后结果为 100。

样例2

输入

1
3
aab

输出

192

说明

字符串 "aab" 中出现过的字母有 a 和 b，种类数 $kind=2$。

相邻字符对：第 1 对 "aa" 相同，不计；第 2 对 "ab" 不同，$diff=1$。

未出现的字母种类 $miss=26-2=24$。

每种可行字母对应原始信息 $2^{diff+2}=2^{3}=8$ 种。

答案 $24 \\times 8 = 192$，取模后为 192。

样例3

输入

1
5
abcde

输出

1344

说明

字符串 "abcde" 包含 5 种不同字母，$kind=5$。

所有相邻字符均不相同，相邻位置数为 4，故 $diff=4$。

未在 $s$ 中出现的字母有 $26-5=21$ 种。

每种对应的原始信息数量为 $2^{diff+2}=2^{6}=64$。

总和为 $21 \\times 64 = 1344$，取模后仍为 1344。