称一个序列 $(a_1,a_2,\cdots,a_n)$ 是避免 120 模式的，当且仅当不存在 $1\leq i<j<k\leq n$ 使得 $a_k<a_i<a_j$。

给定质数 $P$。$q$ 次询问，每次给定 $n,m$，求有多少个长度为 $n$ 的、值域在 $[0,m]$ 内的整数序列 $a$ 是避免 120 模式的，结果对 $P$ 取模。

输入格式

第一行两个整数 $P,q$，表示模数和询问次数。

接下来 $q$ 行，每行两个整数 $n,m$，表示一组询问。

输出格式

输出共 $q$ 行，第 $i$ 行表示第 $i$ 次询问的答案对 $P$ 取模的结果。

样例数据

见下发文件。

数据范围

对于全部数据，满足 $10^8\leq P\leq 10^9$，$1\leq q\leq 8\times 10^4$，$1\leq n\leq 100$，$0\leq m\leq 10^9$。

测试点 $11\sim 20$ 关于 $n$ 和 $q$ 都有梯度。