Binomial Coefficient Modulo (3)

Problem Description

Given a prime $p$. Answer $T$ queries; for each, output the value of ${n \choose m} \bmod p$.

Input Format

The first line contains two integers $p, T$.

The following $T$ lines each contain two integers $n, m$.

Output Format

For each query, output one line containing the answer.

Sample Input

10007 3
5 2
50 20
50000000 20000000

Sample Output

10
2551
0

Constraints

For all data, $1\leq T\leq 10^5$, $1\leq m\leq n\leq 10^{18}$, and $2\leq p \leq 10^6$ are guaranteed, where $p$ is prime.