2025B.md (1597B)
1 Source: https://codeforces.com/problemset/problem/2025/B 2 3 B. Binomial Coefficients, Kind Of 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Recently, akshiM met a task that needed binomial coefficients to solve. He wrote a code he usually does that looked like this: 22 23 ``` 24 for (int n = 0; n < N; n++) { // loop over n from 0 to N-1 (inclusive) 25 C[n][0] = 1; 26 C[n][n] = 1; 27 for (int k = 1; k < n; k++) // loop over k from 1 to n-1 (inclusive) 28 C[n][k] = C[n][k - 1] + C[n - 1][k - 1]; 29 } 30 ``` 31 32 Unfortunately, he made an error, since the right formula is the following: 33 34 ``` 35 C[n][k] = C[n - 1][k] + C[n - 1][k - 1] 36 ``` 37 38 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. 39 40 Since values $C[n_i][k_i]$ may be too large, print them modulo $10^9 + 7$. 41 42 Input 43 44 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. 45 46 The second line contains $t$ integers $n_1, n_2, \dots, n_t$ ($2 \le n_i \le 10^5$). 47 48 The third line contains $t$ integers $k_1, k_2, \dots, k_t$ ($1 \le k_i \lt n_i$). 49 50 Output 51 52 Print $t$ integers $C[n_i][k_i]$ modulo $10^9 + 7$. 53 54 Example 55 56 Input 57 58 ``` 59 7 60 61 2 5 5 100000 100000 100000 100000 62 63 1 2 3 1 33333 66666 99999 64 ``` 65 66 Output 67 68 ``` 69 2 70 4 71 8 72 2 73 326186014 74 984426998 75 303861760 76 ```