题目内容

小明准备输入一个仅由小写英文字母组成的字符串，但他的键盘在一开始就有且仅有一个按键失灵，导致该字母在原串中的所有出现都没有被输入，最终得到的字符串为 $s$。小明还告诉你：原本要输入的完整字符串中任意相邻两个字符都不相同。

请你计算，对于每一个可能的小写字母 $c$（'$a$' 到 '$z$'），有多少个满足条件的原始字符串（删除所有 $c$ 后得到 $s$，且自身相邻字符不同）。请输出将这些情况下得到的数量相加后的总和。由于答案可能很大，结果对 $10^9 + 7$ 取模。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 $T\ (1 \le T \le 10^5)$ 表示数据组数。接下来每组数据描述如下：

• 第一行输入一个整数 $n\ (1 \le n \le 2 \times 10^5)$ 表示字符串的长度。
• 第二行输入一个仅由小写字母组成的字符串 $s$。

保证所有测试数据中字符串长度总和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一个整数，表示“可能的原始字符串”的数量对 $10^9 + 7$ 取模后的结果。

样例1

输入

3
4
abac
4
aaaa
3
xyz

输出

736
100
368