← 返回题目列表

Codeforces · 2025/B

B. 二项式系数,某种

中文机器翻译题面 查看原题

最近,akshiM 遇到一个需要二项式系数求解的任务。他写了一个他通常使用的代码,如下所示:

不幸的是,他犯了一个错误,因为正确的公式如下:

但他的团队成员 keblidA 对使用错误公式生成的值感兴趣。请帮助他计算 $$$t$$$ 各种对 $$$(n_i, k_i)$$$ 的这些系数。请注意,它们应该根据第一个(错误)公式计算。

由于值 $$$C[n_i][k_i]$$$ 可能太大,因此以 $$$10^9 + 7$$$ 为模打印它们。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 对的数量。接下来,$$$t$$$ 对被写成两行。

第二行包含 $$$t$$$ 整数 $$$n_1, n_2, \dots, n_t$$$ ($$$2 \le n_i \le 10^5$$$)。

第三行包含 $$$t$$$ 整数 $$$k_1, k_2, \dots, k_t$$$ ($$$1 \le k_i < n_i$$$)。

输出

打印 $$$t$$$ 整数 $$$C[n_i][k_i]$$$ 模 $$$10^9 + 7$$$。

示例

输入 #1

7
2 5 5 100000 100000 100000 100000
1 2 3 1 33333 66666 99999

输出 #1

2
4
8
2
326186014
984426998
303861760