题目内容

机器人从一条空白的指令序列开始，逐步构建一条目标序列。每一步，机器人会在当前序列的任意位置（包括最前端和最后端）插入一个小写字母。经过 $N$ 次插入后，序列长度变为 $N$。两种操作序列被视为不同，当且仅当存在某一步，插入的位置或插入的字母不同。

给定最终生成的目标序列 $S$，求能生成该目标序列的不同操作序列的数量。答案需要对 $10^9+7$ 取模。可以证明，答案仅与目标序列的长度 $N$ 有关，与字母内容无关。

约束：测试数据组数 $T$ 不超过 $2 \times 10^5$；每组数据中 $1 \le N \le 5 \times 10^5$，且所有组的 $N$ 之和不超过 $2 \times 10^6$。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。接下来每组数据包含两行：第一行包含一个整数 $N$，表示目标序列的长度；第二行包含一个长度为 $N$ 的小写字母字符串 $S$，表示目标序列。

输出描述

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

样例1

输入

1
1
a

输出

1

说明

目标序列长度为 1 时，由于插入操作的顺序完全由反向删除顺序决定，只有 $1$ 种删除顺序，对应正向操作序列数即为 $1! = 1$。字符串内容不影响结果。答案为 1。

样例2

输入

1
3
xyz

输出

6

说明

长度为 3 的序列，反向删除时，第一步有 $3$ 个位置可选，第二步有 $2$ 个，第三步有 $1$ 个，不同的删除顺序数为 $3 \\times 2 \\times 1 = 6$。每种删除顺序唯一对应正向插入顺序，因此答案为 $3! = 6$。

样例3

输入

2
2
ab
5
hello

输出

2
120

说明

第一组数据：长度 $N=2$，答案为 $2! = 2$。 第二组数据：长度 $N=5$，答案为 $5! = 120$。在模数 $10^9+7$ 下，这些较小的阶乘值保持不变。第一行输出 2，第二行输出 120。