AT_tenka1_2014_final_d 高橋君

[problemUrl]: https://atcoder.jp/contests/tenka1-2014-final/tasks/tenka1_2014_final_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 $ 行で出力せよ。出力の末尾には改行をいれること。 ### Sample Explanation 1 $ n=1 $, $ k=1 $ の時、高橋君は、`0`, `1` の $ 2 $ つです。 $ n=3 $, $ k=2 $ の時、高橋君は、`000`, `001`, `010`, `011`, `100`, `101`, `110` の $ 7 $ つです。 大きな数の時には、 $ 1000000007 $ で割った余りを出力することに注意してください。