A sequence $(a_1, a_2, \dots, a_n)$ is said to be 120-pattern-avoiding if and only if there do not exist $1 \leq i < j < k \leq n$ such that $a_k < a_i < a_j$.

Given a prime number $P$ and $q$ queries, for each query given by $n$ and $m$, find the number of integer sequences $a$ of length $n$ with values in the range $[0, m]$ that are 120-pattern-avoiding. The result should be taken modulo $P$.

Input

The first line contains two integers $P$ and $q$, representing the modulus and the number of queries.

Each of the next $q$ lines contains two integers $n$ and $m$, representing a query.

Output

Output $q$ lines, where the $i$-th line is the answer to the $i$-th query modulo $P$.

Examples

Input 1

(input data)

Output 1

(output data)

Constraints

For all test cases, $10^8 \leq P \leq 10^9$, $1 \leq q \leq 8 \times 10^4$, $1 \leq n \leq 100$, and $0 \leq m \leq 10^9$.

The test cases are categorized as follows:

• Test cases 1, 2: $n \leq 16, m \leq 16$
• Test cases 3, 4: $n \leq 18, m \leq 18$
• Test cases 5, 6: $n \leq 18, m \leq 10^9$
• Test cases 7, 8: $n \leq 20, m \leq 20$
• Test cases 9, 10: $n \leq 20, m \leq 10^9$
• Test cases 11–16: $n \leq 100, m \leq 100$
• Test cases 17–20: $n \leq 100, m \leq 10^9$

Test cases 11–20 have gradients for both $n$ and $q$.