1083. 一道难题

有一个长度为 nn 的序列,特征为 mm,满足 a[i]=a[im] (i>m),a[i]=i (im)a[i]=a[i-m] \ (i>m), a[i]=i \ (i \leq m)

1,2,...,m[i]1,m[i],1,2,...,m[i]1,m[i],...(ni) mod (m[i]+1)1,2,...,m[i]-1 ,m[i],1,2,...,m[i]-1,m[i],...(n-i) \ mod \ (m[i]+1)

例如 n=7,m=3n=7,m=3 时,序列如下:

1,2,3,1,2,3,11 ,2, 3, 1, 2, 3, 1

现可删除若干元素(也可以不删,也可以全删),问会出现多少不同的序列? 序列不同当且仅当长度不一致或者某一位不同。

答案对 109+710^9+7 取模,即 ans % 1000000007ans \ \% \ 1000000007

输入

第一行输入一个 T (1T1000)T \ (1 \leq T \leq 1000),表示 TT 组数据。

输入两个整数 n,m (1m,n2×105)n,m \ (1 \leq m,n \leq 2 \times 10^5)

保证输入的 nn 的总和不超过 2×1052 \times 10^5

输出

输出会出现多少不同的序列。

样例

标准输入 复制文本
2
6 1
4 3
标准输出 复制文本
7
15

来源

广东工业大学 2020 年 ACM 第一次月赛

登录以提交代码。
单点时限 2 秒
内存限制 128 MB
提交 69
通过 22