题目描述

你有一个随机生成器，每次会均匀随机地生成一个 $[0,m]$ 之间的整数。你用这个随机生成器生成了 $2n$ 个整数，你想知道你生成的前 $n$ 个整数的和比后 $n$ 个整数的和大的概率是多少。

你只需求出这个概率对质数 $P$ 取模后的结果即可。

输入格式

每个测试点有多组询问，但用的都是同一个模数。

第一行一个整数 $P$ 表示这个测试点所用的模数。

第二行一个整数 $T$ 表示询问组数。

接下来 $T$ 行，每行两个整数，分别表示每组询问的 $n$ 和 $m$。

输出格式

输出共 $T$ 行，每行一个整数表示答案。

输入输出样例 #1

输入 #1

998244353
5
1 2
3 4
25 25
114 514
1919 810

输出 #1

332748118
675356228
865314458
846704265
499065697

说明/提示

样例一解释

对于第一组询问，满足条件当且仅当生成的 $2n$ 个整数为 $[2,0],[2,1],[1,0]$ 三种情况之一，概率为 $\dfrac{3}{(m+1)^{2n}}=\dfrac{1}{3}$，对 $998244353$ 取模后的结果为 $332748118$。

数据范围

本题共 $10$ 个测试点，每个测试点 $10$ 分。

对于所有测试点，保证 $1\le T,n,m\le2000,10^8\le P\le10^9$，且 $P$ 是质数。

对于测试点 $1$：$1\le T,n,m\le5$。

对于测试点 $2,3$：$1\le T,n,m\le15$。

对于测试点 $4,5$：$1\le T,n,m\le50$。

对于测试点 $6,7$：$1\le T,n,m\le200$。

对于测试点 $8,9$：$1\le T,n,m\le1000$。

对于测试点 $10$：无特殊限制。