시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 12 | 3 | 3 | 30.000% |
Let $M$ be the set of integers at most $n$ by absolute value, that is, $M = \{ x \in \mathbb{Z}\colon |x| \le n \}$.
Let $f_k (x)$ be the function $f$ applied $k$ times to an initial value $x$, that is, $f_0 (x) = x$ and $f_i (x) = f (f_{i - 1} (x))$ for any $i \ge 1$.
Given the integers $n$ and $k$, count the number of functions $f (x)$ satisfying the following conditions:
As the answer may be very large, print it modulo $10^9 + 7$.
The first line of input contains an integer $T$, the number of test cases ($1 \le T \le 100$).
Each test case contains a pair of positive integers $n$ and $k$ ($n \cdot k \le 10^9$).
The total sum of $n \cdot k$ over all test cases does not exceed $4 \cdot 10^9$.
For each test case, output the answer modulo $10^9 + 7$ on a separate line.
7 1 1 2 1 100 1 1 2 2 2 3 2 20 4
1 1 1 0 2 0 1048576
If $k = 1$, only the function $f(x) = -x$ satisfies all requirements.
If $n = k = 2$, two functions exist: