SP8277 PSTR - Number of Prime Strings
题目描述
如果一个字符串不能表示为多个相同字符串的连接，则称其为「素数字符串」。例如，字符串 AAA、ABABAB 和 CFGFGCFGFG 不是素数字符串，而 CFGFGC 和 ABABA 是素数字符串。你的任务是计算长度为 $N$（$1 \le N \le 1000000$）且只由前 $K$（$1 \le K \le 26$）个英文字母组成的素数字符串的数量。注意，这些 $K$ 个字母并不需要全部在字符串中出现。
输入格式
有多组测试数据。第一行提供了测试数据的总数（大约 10000 组）。接下来的每一行对应一组测试数据，其中包含两个整数 $K$ 和 $N$，它们之间用空格分隔。
输出格式
对于每个测试数据组，在单独的一行输出其对应的素数字符串数量，并将结果对 $1000000007$ 取模。
### 示例
```
输入：
1
2 3
输出：
6
说明
只含有字符 'A' 和 'B' 且长度为 3 的素数字符串有：AAB, ABA, ABB, BAA, BAB, BBA。
```
说明/提示
- $1 \le K \le 26$
- $1 \le N \le 1000000$
**本翻译由 AI 自动生成**