Binomial Coefficient Modulo 4

Problem Description

You are given a modulus $q$. Answer $T$ queries; for each query output the value of ${n \choose m} \bmod q$.

Input Format

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

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

Output Format

For each query, output one line: the answer.

Sample Input

10000 3
5 2
50 20
50000000 20000000

Sample Output

10
3960
8800

Constraints

For all data, $1 \leq T \leq 10^5$, $1 \leq m \leq n \leq 10^{18}$, $2 \leq q \leq 10^6$.