提示: 欢迎访问OurACM平台。
Problem 2200 cleaning

Accept: 107    Submit: 212
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

N个人围成一圈在讨论大扫除的事情,需要选出K个人。但是每个人与他距离为2的人存在矛盾,所以这K个人中任意两个人的距离不能为2,他们想知道共有多少种方法。

Input

第一行包含一个数T(T<=100),表示测试数据的个数。

接下来每行有两个数N,K,N表示人数,K表示需要的人数(1<=N<=1000,1<=K<=N)。

Output

输出满足题意的方案数,方案数很大,所以请输出方案数mod 1,000,000,007 后的结果。

Sample Input

2 4 2 8 3

Sample Output

4 16

Source

FOJ有奖月赛-2015年10月

Submit  Back  Status  Discuss