B、题目描述

你有一个随机生成器，每次会均匀随机地生成一个[0,m]之间的整数。你用这个随 机生成器生成了2n个整数，你想知道你生成的前n个整数的和比后n个整数的和大的 概率是多少。你只需求出这个概率对质数P取模后的结果即可

输入格式

从文件pr.in中读入数据。 每个测试点有多组询问，但用的都是同一个模数。 第一行一个整数P表示这个测试点所用模数。 第二行一个整数T表示询问组数。 接下来T行每行两个整数分别表示每组询问的n和m。

输出格式

输出到文件pr.out中。 共T行，每行一个整数表示答案

Samples

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

332748118
675356228
865314458
846704265
499065697

样例1解释

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

数据范围

本题共有10个测试点，每个测试点10分。 对于所有测试点，保证1≤T,n,m≤2000,10^8 ≤P ≤10^9，且 P 是质数。 • 对于测试点1，有1≤T,n,m≤5。 • 对于测试点2,3，有1≤T,n,m≤15。 • 对于测试点4,5，有1≤T,n,m≤50。 • 对于测试点6,7，有1≤T,n,m≤200。 • 对于测试点8,9，有1≤T,n,m≤1000。 • 对于测试点10，无特殊限制