https://codeforces.com/contest/1514/problem/A
시간 1초, 메모리 256MB

input :

• t (1≤t≤10)
• n k (1≤n≤105, 1≤k≤20).

output :

• 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 109+7.
  각 테스트 케이스에서 조건에 부응하는 정답을 출력하시오. 수가 매우 크니 109 + 7의 나머지를 출력하시오.

조건 :

• Given two integers n and k, count the number of arrays of length n such that:

all its elements are integers between 0 and 2k−1 (inclusive);
the bitwise AND of all its elements is 0;
the sum of its elements is as large as possible.
n 과 k 두 수를 받았을 때 가능한 배열의 수를 카운팅 하시오.
모든 원소들은 0 ~ 2k−1 사이의 값입니다.
모든 원소들을 AND 연산을 했을때의 결과는 0이어야 합니다.
모든 원소의 합은 가능한 커야 합니다.

---

AND 연산

이 연산의 결과가 0이 되어야 한다. 이 의미는 최소한 0을 가지고 있던가 아니면 다른 두 숫자를 통해서 0을 만들 수 있어야 한다.

최댓값

최댓값을 유지 하기 위해서는 0 n - 1로 구성된 배열을 만들 수 있다.
그리고 이 값을 유지하면서 수행해 나가야 한다.

경우의 수

가능한 숫자들은 무엇이 있을 까.

배열에 들어가는 수들은 모두 k비트 내의 이진수로 표현이 가능하다.
그리고 내가 제일 처음 생각했던
0, n - 1
1, n - 2
...
외에도 다른 경우가 존재한다.

여러 숫자들이 나눠서 0(비트 값)을 가지고 있어 연산을 통해 합쳐질 수 있기 때문이다.

그래서 0을 어떻게 가지고 있게 할 수 있는지를 찾는 것이 이 문제의 해결책이다.
우리가 가질 수 있는 숫자는 n개이다.
이 숫자들이 가지는 비트는 k개이다.

비트의 위치

각 비트의 위치에서 0이 될 위치를 고르는 경우는?
n개이다.

_ _ _ 4비트짜리 숫자.
를 n개 가지고 있음.

_

...

그렇다면 이 빈칸들 중에 1개를 고를 수 있기 때문에 n이 되는 것이고.
이를 비트의 수만큼 해야 하기 때문에 k번 반복해야 하는 것이다.

import sys
import math

t = int(sys.stdin.readline())
for _ in range(t):
    n, k = map(int, sys.stdin.readline().split())

    ans = 1
    for i in range(k):
        ans = (ans * n) % int(math.pow(10, 9) + 7)
    print(ans)