← 返回题目列表

AtCoder · tenka1_2014_final_d

D. 高桥君

中文机器翻译题面 查看原题

問題文

文字列 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 后的余数。