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