B. Биномиальные коэффициенты, ну типа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно акшиМ столкнулся с задачей, для решения которой нужны были биномиальные коэффициенты. Он написал код, который выглядел так:

    for (int n = 0; n < N; n++) { // цикл по n от 0 до N-1 включительно
        C[n][0] = 1;
        C[n][n] = 1;
        for (int k = 1; k < n; k++) // цикл по k от 1 до n-1 включительно
            C[n][k] = C[n][k - 1] + C[n - 1][k - 1];
    }

К сожалению, он допустил ошибку, так как правильная формула следующая:

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

Но его сокомандник, кеблидА, заинтересовался значениями, которые были получены с использованием неправильной формулы. Пожалуйста, помогите ему вычислить эти коэффициенты для $$$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$$$.

Пример
Входные данные
7
2 5 5 100000 100000 100000 100000
1 2 3 1 33333 66666 99999
Выходные данные
2
4
8
2
326186014
984426998
303861760