#P18699. Perfect Strings

    ID: 18035 传统题 3000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-栈Catalan 数普通生成函数生成函数求系数线性 DP逆元线性递推

Perfect Strings

Perfect Strings

考虑一个大小为 cc 的字符集 σ\sigma。由这个字符集中的字符组成的长度为 2n2n 的字符串,共有 c2nc^{2n} 个。

如果字符串 SS 的下标集合 {1,2,…,2n}\{1,2,\ldots,2n\} 能够划分成 nn 个配对,并满足以下条件,就称 SS 是完美字符串:

  • 每个下标恰好属于一个配对。
  • 对每个配对 (i,j)(i,j),有 S[i]=S[j]S[i]=S[j]。
  • 任意两个配对都不相互交错。即对于两个配对 (i,j)(i,j) 和 (k,l)(k,l)(各对中较小的下标写在前面),不能出现 i<k<j<li<k<j<l。

给定 n,cn,c,求长度为 2n2n、字符均来自 σ\sigma 的完美字符串个数,对 109+710^9+7 取模。

输入格式

第一行包含整数 TT,表示测试用例数。

接下来 TT 行,每行包含两个整数 n,cn,c。

数据范围

  • 1≤T≤1051\le T\le10^5。
  • 1≤n,c≤1071\le n,c\le10^7。
  • 所有测试用例中,nn 的总和不超过 10710^7。

输出格式

对每个测试用例输出一行,表示所求字符串个数对 109+710^9+7 取模的结果。

样例输入

2
3 1
2 2

样例输出

1
6

样例说明

第一个测试用例中,只有一个字符串,它显然是完美的。

第二个测试用例中,令字符集为 {a,b}\{a,b\}。所有完美字符串,以及各自的一种配对方案如下:

字符串 一种合法配对
aaaa {(1,4),(2,3)}\{(1,4),(2,3)\}
aabb {(1,2),(3,4)}\{(1,2),(3,4)\}
abba {(1,4),(2,3)}\{(1,4),(2,3)\}
baab
bbaa {(1,2),(3,4)}\{(1,2),(3,4)\}
bbbb