#P18699. Perfect Strings
Perfect Strings
Perfect Strings
考虑一个大小为 的字符集 。由这个字符集中的字符组成的长度为 的字符串,共有 个。
如果字符串 的下标集合 能够划分成 个配对,并满足以下条件,就称 是完美字符串:
- 每个下标恰好属于一个配对。
- 对每个配对 ,有 。
- 任意两个配对都不相互交错。即对于两个配对 和 (各对中较小的下标写在前面),不能出现 。
给定 ,求长度为 、字符均来自 的完美字符串个数,对 取模。
输入格式
第一行包含整数 ,表示测试用例数。
接下来 行,每行包含两个整数 。
数据范围
- 。
- 。
- 所有测试用例中, 的总和不超过 。
输出格式
对每个测试用例输出一行,表示所求字符串个数对 取模的结果。
样例输入
2
3 1
2 2
样例输出
1
6
样例说明
第一个测试用例中,只有一个字符串,它显然是完美的。
第二个测试用例中,令字符集为 。所有完美字符串,以及各自的一种配对方案如下:
| 字符串 | 一种合法配对 |
|---|---|
aaaa |
|
aabb |
|
abba |
|
baab |
|
bbaa |
|
bbbb |