K. Mood Swings
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is tracking her mood swings for the next $$$n$$$ days. Each day her mood will randomly be either bad ($$$0$$$) or good ($$$1$$$), independently with equal probability.

After $$$n$$$ days, Alice looks back at the sequence of moods and wants to remember a period where her mood only improves or stays the same. To do this, she selects a subsequence$$$^{\text{∗}}$$$ of days such that her mood never gets worse as time goes forward. In other words, once she chooses a day with mood $$$1$$$, she cannot later choose a day with mood $$$0$$$.

Among all such subsequences, Alice always chooses one with the maximum possible length. Let $$$f(S)$$$ denote this length for a mood sequence $$$S$$$.

Since the moods are generated randomly, Alice wonders what value to expect.

Formally, consider all binary strings $$$S$$$ of length $$$n$$$, each occurring with probability $$$\frac{1}{2^n}$$$. Compute the expected value of $$$f(S)$$$.

$$$^{\text{∗}}$$$A subsequence of a sequence is obtained by deleting zero or more elements without changing the order of the remaining elements.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first and only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$10^8 \le m \le 10^9$$$).

It is guaranteed that $$$m$$$ is prime.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output the expected value of $$$f(S)$$$ modulo $$$m$$$.

Formally, let the expected value be written as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not\equiv 0 \pmod m$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod m$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt m$$$ and $$$x \cdot q \equiv p \pmod m$$$.

Example
Input
3
1 100000007
2 100000037
4 100000039
Output
1
25000011
68750030
Note

In the first test case, $$$n = 1$$$. The possible mood sequences are:

  • $$$0$$$ with $$$f(S) = 1$$$
  • $$$1$$$ with $$$f(S) = 1$$$
In both cases, the longest valid subsequence has length $$$1$$$. Therefore, the expected value is $$$1$$$.

In the second test case, $$$n = 2$$$. The possible mood sequences are:

  • $$$00$$$ with $$$f(S) = 2$$$
  • $$$01$$$ with $$$f(S) = 2$$$
  • $$$10$$$ with $$$f(S) = 1$$$
  • $$$11$$$ with $$$f(S) = 2$$$
The expected value is $$$\frac{2 + 2 + 1 + 2}{4} = \frac{7}{4}$$$.

In the third test case, $$$n = 4$$$. The expected value of $$$f(S)$$$ over all $$$2^4$$$ binary strings equals $$$\frac{51}{16}$$$.