codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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