1514B.md (1235B)
1 Source: https://codeforces.com/problemset/problem/1514/B 2 3 B. AND 0, Sum Big 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Baby Badawy's first words were "AND 0 SUM BIG", so he decided to solve the following problem. Given two integers $n$ and $k$, count the number of arrays of length $n$ such that: 22 23 * all its elements are integers between $0$ and $2^k-1$ (inclusive); 24 * the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of all its elements is $0$; 25 * the sum of its elements is as large as possible. 26 27 Since the answer can be very large, print its remainder when divided by $10^9+7$. 28 29 Input 30 31 The first line contains an integer $t$ ($1 \le t \le 10$) — the number of test cases you need to solve. 32 33 Each test case consists of a line containing two integers $n$ and $k$ ($1 \le n \le 10^{5}$, $1 \le k \le 20$). 34 35 Output 36 37 For each test case, print the number of arrays satisfying the conditions. Since the answer can be very large, print its remainder when divided by $10^9+7$. 38 39 Example 40 41 Input 42 43 ``` 44 2 45 2 2 46 100000 20 47 ``` 48 49 Output 50 51 ``` 52 4 53 226732710 54 ``` 55 56 Note 57 58 In the first example, the $4$ arrays are: 59 60 * $[3,0]$, 61 * $[0,3]$, 62 * $[1,2]$, 63 * $[2,1]$.