#ARC116C. Multiple Sequences
Multiple Sequences
Multiple Sequences
时间限制:2s
空间限制:1024MB
题目描述
给定整数 ,求满足下列条件的长度为 的整数序列 的数量:
- 对所有 ,都有 ;
- 对所有 , 是 的倍数。
答案可能很大,请输出其对 取模的结果。
输入格式
一行两个整数 。
输出格式
输出一个整数,表示答案对 取模的结果。
样例输入 1
3 4
样例输出 1
13
样例输入 2
20 30
样例输出 2
71166
样例输入 3
200000 200000
样例输出 3
835917264
数据范围
对于所有数据,。
| 子任务编号 | 分值 | 特殊限制 |
|---|---|---|
| 1 | 10 | |
| 2 | 15 | , |
| 3 | 20 | |
| 4 | 25 | |
| 5 | 30 | 无特殊限制 |