高橋君
题意翻译
$m$ 组询问,每次给定 $n,k$,求 $\sum\limits_{i=0}^k \binom{n}{i}$。
$1 \le n, m, k \le 10^5$。
题目描述
[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 $ 行で出力せよ。出力の末尾には改行をいれること。
输入输出样例
输入样例 #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
说明
### 部分点
$ 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 $ で割った余りを出力することに注意してください。