AT_tenka1_2014_final_d 高橋君

当且仅当字符串 $S$ 满足以下条件时，称其为“高桥君”： - $S$ 是仅由 `0` 和 `1` 组成的字符串。 - $S$ 的长度恰好为 $n$。 - $S$ 中包含的 `1` 的个数不超过 $k$。 请计算“高桥君”的个数，并输出其对 $1000000007$ 取模后的结果。

输入通过标准输入给出，格式如下： - 第 $1$ 行包含一个整数 $T\ (1 \leq T \leq 100000)$，表示测试用例的数量。 - 接下来的 $T$ 行，每行包含两个整数 $n$ 和 $k$，用空格隔开，表示每个测试用例的条件 $n_i,\ k_i\ (0 \leq k_i \leq n_i \leq 100000)$。

对于每个测试用例，输出“高桥君”的个数对 $1000000007$ 取模后的结果，每个结果占一行。输出末尾需换行。

## 部分分 若能正确解决所有满足 $0 \leq k_i \leq n_i \leq 3000$ 的测试用例，可获得 $50$ 分。 若能正确解决所有测试用例，可再获得 $150$ 分。 对于每个测试用例，输出“高桥君”的个数对 $1000000007$ 取模后的结果，每个结果占一行。输出末尾需换行。 ## 样例解释 1 当 $n=1$，$k=1$ 时，“高桥君”有 `0`、`1` 共 $2$ 个。当 $n=3$，$k=2$ 时，“高桥君”有 `000`、`001`、`010`、`011`、`100`、`101`、`110` 共 $7$ 个。注意在数值较大时，需要输出对 $1000000007$ 取模的结果。 由 ChatGPT 4.1 翻译