最近,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