B. Binomial Coefficients, Kind Oftime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputRecently, akshiM met a task that needed binomial coefficients to solve. He wrote a code he usually does that looked like this: 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]; }Unfortunately, he made an error, since the right formula is the following: C[n][k] = C[n - 1][k] + C[n - 1][k - 1]But his team member keblidA is interested in values that were produced using the wrong formula. Please help him to calculate these coefficients for $$$t$$$ various pairs $$$(n_i, k_i)$$$. Note that they should be calculated according to the first (wrong) formula.Since values $$$C[n_i][k_i]$$$ may be too large, print them modulo $$$10^9 + 7$$$.InputThe first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of pairs. Next, $$$t$$$ pairs are written in two lines.The second line contains $$$t$$$ integers $$$n_1, n_2, \dots, n_t$$$ ($$$2 \le n_i \le 10^5$$$).The third line contains $$$t$$$ integers $$$k_1, k_2, \dots, k_t$$$ ($$$1 \le k_i < n_i$$$).OutputPrint $$$t$$$ integers $$$C[n_i][k_i]$$$ modulo $$$10^9 + 7$$$.ExampleInput72 5 5 100000 100000 100000 1000001 2 3 1 33333 66666 99999Output2
4
8
2
326186014
984426998
303861760