D - 高橋君

Time Limit: 6 sec / Memory Limit: 256 MB

問題文

文字列 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, 12 つです。

n=3, k=2 の時、高橋君は、000, 001, 010, 011, 100, 101, 1107 つです。

大きな数の時には、 1000000007 で割った余りを出力することに注意してください。


Source Name

天下一プログラマーコンテスト2014 本戦