함수 세기

정수 $n$에 대해 절댓값이 $n$ 이하인 정수들의 집합을 $M = \{ x \in \mathbb{Z} : |x| \le n \}$라고 하자.

$f_k(x)$는 초깃값 $x$에 함수 $f$를 $k$번 적용한 값이다. 즉, $f_0(x) = x$이고, 임의의 $i \ge 1$에 대해 $f_i(x) = f(f_{i-1}(x))$이다.

정수 $n$과 $k$가 주어질 때, 다음 조건을 모두 만족하는 함수 $f(x)$의 개수를 구하라.

1. $f: M \to M$
2. $\forall x \in M: f_k(x) = -x$
3. $\forall x \in M: \big| |f(x)| - |x| \big| \le 2$

답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트 케이스는 양의 정수 $n$과 $k$의 쌍으로 주어진다 ($n \cdot k \le 10^9$).

모든 테스트 케이스에 대한 $n \cdot k$의 합은 $4 \cdot 10^9$를 넘지 않는다.

각 테스트 케이스마다 답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

$k = 1$이면 조건을 모두 만족하는 함수는 $f(x) = -x$뿐이다.

$n = k = 2$이면 조건을 만족하는 함수는 두 개 있다.

• $(-2, -1, 0, 1, 2) \to (1, -2, 0, 2, -1)$
• $(-2, -1, 0, 1, 2) \to (-1, 2, 0, -2, 1)$