Background

There should have been a brilliant background story here, but unfortunately, there was not enough space to write it down.

Description

Given a number line, you start at the origin.

In each unit of time, you move one unit to the left, stay put, or move one unit to the right with probabilities $\frac{1}{4}, \frac{1}{2}, \frac{1}{4}$, respectively.

There are $T$ queries. For each query, given $n$, calculate the expected value of the displacement magnitude (i.e., the absolute value of the coordinate) after $n$ units of time, modulo $p$.

Implementation Details

Please include #include "pilgrimage.h" before submitting your source code.

You need to implement the following functions:

void init (int o, int p);

• $o$: Represents the subtask number of the current test case. Specifically, $o = 0$ for the sample.
• $p$: Represents the modulus for the current test case.

This function will be called exactly once per test case, before any ask calls.

int ask (long long n);

• $n$: Represents the time duration for a query.
• This function should return an integer in the range $[0, p)$ representing the answer.

Example Grader

The example grader reads the input data in the following format:

• Line 1: $o ~ T ~ p$, where $o$ is the subtask number.
• Line $2 + i$ ($0 \le i < T$): $n[i]$.

The example grader first calls init, then calls ask in the order $i = 0, 1, \dots, T - 1$: $n = n[i]$.

The example grader outputs the result in the following format:

Line $1 + i$ ($0 \le i < T$): An integer in the range $[0, p)$, representing the result returned by the $i$-th call to ask.

Examples

Input 1

0 9 999983
1
2
3
4
5
12
2999
999999
1000000000000000000

Output 1

499992
749988
937485
593741
292965
279604
703253
798000
771553

Note

Taking $n = 2$ as an example, there are $9$ possible outcomes:

• Move left in the first unit, move left in the second unit, final position $-2$, probability $\frac{1}{16}$.
• Move left in the first unit, stay in the second unit, final position $-1$, probability $\frac{1}{8}$.
• Move left in the first unit, move right in the second unit, final position $0$, probability $\frac{1}{16}$.
• Stay in the first unit, move left in the second unit, final position $-1$, probability $\frac{1}{8}$.
• Stay in the first unit, stay in the second unit, final position $0$, probability $\frac{1}{4}$.
• Stay in the first unit, move right in the second unit, final position $1$, probability $\frac{1}{8}$.
• Move right in the first unit, move left in the second unit, final position $0$, probability $\frac{1}{16}$.
• Move right in the first unit, stay in the second unit, final position $1$, probability $\frac{1}{8}$.
• Move right in the first unit, move right in the second unit, final position $2$, probability $\frac{1}{16}$.

Thus, the expected value is $\lvert -2 \rvert \times \frac{1}{16} + \lvert -1 \rvert \times \frac{1}{8} + \dots + \lvert 2 \rvert \times \frac{1}{16} = \frac{3}{4}$, which is $749988$ modulo $999983$.

Constraints

For all test cases, $3 \le p \le 10 ^ 6$, $1 \le T \le 10 ^ 6$, $1 \le n \le 10 ^ {18}$, and $p$ is guaranteed to be odd.

The specific constraints for each subtask are shown in the table below:

• Property A: $p$ is a prime number.
• Property B: $p = p_1 \times p_2 \times \dots \times p_k$, where $p_1, p_2, \dots, p_k$ are distinct prime numbers.