题目内容

给你一个长度为 $n$的字符串 $s$。我们按照如下过程从空串构造字符串：共进行 $n$次操作，每次在当前字符串的任意位置插入一个小写字母。问一共有多少种不同的操作序列，使得可以最终得到字符串$s$。

两个操作序列不同，当且仅当在某一步操作中，选择的插入位置或插入的小写字母不同。由于答案可能很大，请将答案对$(10^9 + 7)$ 取模后输出。

一次 “在任意位置插入一个小写字母”，指选择当前串中 $[0, \text{length}]$之间的任意位置，将一个小写字母插入到该位置，使得串长度增加$1$。经过$n$ 次插入后，最终串应与给定的 $s$完全相同。

输入描述

每个测试文件均包含多组测试数据。

• 第一行输入一个整数 $T\ (1 \le T \le 2 \times 10^5)$表示测试组数。

• 随后对于每组测试数据：

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

除此之外，保证单个测试文件的$n$之和不超过 $2 \times 10^6$。

输出描述

对于每组测试数据，输出一行一个整数，表示不同的操作序列数量对 $10^9 + 7$ 取模的结果

样例1

输入

2
1
a
3
aba

输出

1
6

说明

第一组：$n=1$，只有一次插入，答案为 $1$。 第二组：总共有 $6$种不同的操作序列可以得到字符串 $aba$。