D - 高橋君
Editorial
/ 
/ 
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, 1 の 2 つです。
n=3, k=2 の時、高橋君は、000, 001, 010, 011, 100, 101, 110 の 7 つです。
大きな数の時には、 1000000007 で割った余りを出力することに注意してください。