组合数取模4

题目描述

给定一个$q$。回答$T$组询问，输出${n \choose m} \bmod q$的值。

输入格式

第一行两个整数$q, T$。

接下来$T$行，每行两个整数$n, m$。

输出格式

对于每组数据，输出一行，表示答案。

样例输入

10000 3 
5 2
50 20
50000000 20000000

样例输出

10
3960
8800

数据范围

对于所有数据，保证$1\leq T\leq 10^5, 1\leq m\leq n\leq 10^{18}, 2\leq q \leq 10^6$。