Recently, akshiM met a task that needed binomial coefficients to solve. He wrote a code he usually does that looked like this:

Unfortunately, he made an error, since the right formula is the following:

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$.

Input

The 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$).

Output

Print $t$ integers $C[n_i][k_i]$ modulo $10^9 + 7$.

见题面 Input 部分

见题面 Output 部分