组合数取模3

题目描述

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

输入格式

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

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

输出格式

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

样例输入

10007 3 
5 2
50 20
50000000 20000000

样例输出

10
2551
0

数据范围

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