有一个长度为 n 的序列,特征为 m,满足 a[i]=a[i−m] (i>m),a[i]=i (i≤m)。
即 1,2,...,m[i]−1,m[i],1,2,...,m[i]−1,m[i],...(n−i) mod (m[i]+1) 。
例如 n=7,m=3 时,序列如下:
1,2,3,1,2,3,1
现可删除若干元素(也可以不删,也可以全删),问会出现多少不同的序列? 序列不同当且仅当长度不一致或者某一位不同。
答案对 109+7 取模,即 ans % 1000000007。
第一行输入一个 T (1≤T≤1000),表示 T 组数据。
输入两个整数 n,m (1≤m,n≤2×105)
保证输入的 n 的总和不超过 2×105。