#P7002. [2017年成都七中集训]尘封的花环

    ID: 6833 传统题 1000ms 512MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>难度分类省选/NOI-组合数学Burnside 引理数论欧拉函数线性代数与代数线性递推快速幂Miller–RabinPollard–Rho扩大模数后精确整除模逆元快速乘防溢出CF2600

[2017年成都七中集训]尘封的花环

尘封的花环

时间限制:2秒。空间限制:128MB。

题目背景

很久以前,春天使者 xuruifan 编织了一枚花环,却因无人欣赏而被尘封。neither_nor 希望让它重见天日,需要知道花环有多少种可能的形态。

题目描述

花环有 nn 朵花,可以使用 kk 种花,相邻的两朵花必须属于不同种类,不要求每种花都出现。能通过旋转重合的两个花环视为同一种。

求不同花环的数量,对 998244353998244353 取模。n=1n=1 时,只有一朵花,按 kk 种选择计数。

输入格式

第一行一个整数 TT,表示数据组数。

接下来 TT 行,每行两个正整数 n,kn,k。

输出格式

输出 TT 行,每行一个整数,表示对应答案模 998244353998244353 的值。

样例输入1

3
4 5
5 6
6 8

样例输出1

70
624
19684

数据范围

记 mod=998244353\mathrm{mod}=998244353。

测试点 nn 上界 kk 上界 TT 上界 特殊限制
1 66 88 55 无
2 22 10610^6
3 33
4 66
5 10310^3
6 10410^4
7 10510^5
8 10610^6
9 10710^7
10 10810^8
11 10910^9 10910^9 nn 与 mod\mathrm{mod} 互质
12 101010^{10}
13 101210^{12}
14 101410^{14}
15—16 101610^{16}
17—18 101810^{18} 2020 nn 的最大质因子不超过 10310^3
19—20 nn 与 mod\mathrm{mod} 互质