Migrated from Lutece 619 吴神,人类的希望

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

公元18906416年，由于歌者无节制的使用二向箔，整个宇宙都将不可避免的跌入二次元。为了拯救学弟们，吴神决定使用一种叫smxrwzdx的基本粒子创造一个新的宇宙，吴神发现，用不同数量的smxrwzdx可以组合成不同的粒子，比如用两个smxrwzdx就可以组成一个魔理沙，三个smxrwzdx就可以组成一个洛天依，总之，无论怎样组合，都会产生一个好的结果（不要吐槽，吴神就是有这么神），现在吴神有$n$个smxrwzdx粒子，为了保持新宇宙的稳定性，吴神要求所组成每一种物质都必须至少包含$k$个smxrwzdx粒子，现在吴神想知道的是，如果他有$n$个smxrwzdx，有多少种不同的世界能够被创造出来。比如吴神有$6$个smxrwzdx，$k$为$2$。那么吴神可以有$4$种方案：$(2,2,2)$, $(4,2)$, $(3,3)$, $(6)$。

Input

第一行有个整数$T$，代表数据组数（$T\leq 10^6$）

接下来有$T$行，每行有两个整数$n$ $k$ ($1\leq n,k\leq 1000$)

Output

每组数据输出一行，表示吴神有多少种不同的世界能够被创造出来，由于答案可能很大，所以答案要模$10^9+7$。

Samples

3 
2 1 
4 2 
6 2

2 
2 
4

Resources

UESTC Training for Math