#P7002. [2017年成都七中集训]尘封的花环
[2017年成都七中集训]尘封的花环
尘封的花环
时间限制:2秒。空间限制:128MB。
题目背景
很久以前,春天使者 xuruifan 编织了一枚花环,却因无人欣赏而被尘封。neither_nor 希望让它重见天日,需要知道花环有多少种可能的形态。
题目描述
花环有 朵花,可以使用 种花,相邻的两朵花必须属于不同种类,不要求每种花都出现。能通过旋转重合的两个花环视为同一种。
求不同花环的数量,对 取模。 时,只有一朵花,按 种选择计数。
输入格式
第一行一个整数 ,表示数据组数。
接下来 行,每行两个正整数 。
输出格式
输出 行,每行一个整数,表示对应答案模 的值。
样例输入1
3
4 5
5 6
6 8
样例输出1
70
624
19684
数据范围
记 。
| 测试点 | 上界 | 上界 | 上界 | 特殊限制 |
|---|---|---|---|---|
| 1 | 无 | |||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 | ||||
| 6 | ||||
| 7 | ||||
| 8 | ||||
| 9 | ||||
| 10 | ||||
| 11 | 与 互质 | |||
| 12 | ||||
| 13 | ||||
| 14 | ||||
| 15—16 | ||||
| 17—18 | 的最大质因子不超过 | |||
| 19—20 | 与 互质 | |||