問題文
文字列 S 被称为高桥。
- S 是 可以表示为
0,1组成的字符串。- S 的长度正好是 n 。
- S 最多是 k 的 您可以创建一个包含
1。
高桥的号码 除以 1000000007 求余数。
入力
输入是按以下格式从标准输入给出的。
T n_1 k_1 n_2 k_2 : n_T k_T
- 1 行包含一个表示测试用例数量的整数。 T\ (1≦T≦100000) 。 表示
- 2 从行 T 行是与高桥病情相关的整数。 n, k是 1 为每一行给出。其中 高桥的第 i 行中, i 次测试的条件 n_i, k_i\ (0≦k_i≦n_i≦100000) 用空格分隔。
出力
高桥的号码 除以 1000000007 后的余数为 1 一行一行, 如果所有满足 T 行。在输出末尾添加换行符。
部分点
0≦k_i≦n_i≦3000 条件的测试用例都被正确回答, 获得 50 点。
如果所有测试用例都回答正确, 高桥君 150 点。
高桥的号码 除以 1000000007 后的余数为 1 一行一行, 如果所有满足 T 行。在输出末尾添加换行符。
入力例1
10 1 1 3 2 5 2 8 3 12 0 642 246 2222 999 2525 21 50000 25000 100000 100000
出力例1
2 7 16 93 1 321969783 856998846 371661809 969409843 607723520
n=1, k=1 时,0, 1 可以得到第 2 一。
请注意,无法创建
n=3, k=2 时,000, 001, 010, 011, 100, 101, 110 可以得到第 7 一。
请注意,无法创建
当数量很大时, 请注意,它会打印除以 1000000007 后的余数。