题目描述

最近，akshiM 遇到了一个需要用到二项式系数来解决的任务。他像往常一样写了如下代码：

    for (int n = 0; n < N; n++) { // loop over n from 0 to N-1 (inclusive)  
        C[n][0] = 1;  
        C[n][n] = 1;  
        for (int k = 1; k < n; k++) // loop over k from 1 to n-1 (inclusive)  
            C[n][k] = C[n][k - 1] + C[n - 1][k - 1];  
    }  

不幸的是，他犯了一个错误，因为正确的公式应该是：

            C[n][k] = C[n - 1][k] + C[n - 1][k - 1]  

但是他的队友 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$ 取模。

说明/提示

由 ChatGPT 4.1 翻译

样例

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

2
4
8
2
326186014
984426998
303861760