1331: 趣味三角
内存限制：128 MB
时间限制：1.000 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
今天，新高一的OIer们第一次进入了机房。z老师想让他们喜欢上OI，于是给了他们每个人一个三角形。这时候，小q突发奇想，拿着手中的三角形，给大家出了一道题，请你帮助他们给小q一个正确的答案。
小q给了你两个整数m，n。请输出杨辉三角前n行的所有数的和模m的值。如果你不知道杨辉三角是什么，请看样例解释。
杨辉三角如下：第一行：1
第二行：1 1
第三行：1 2 1
第四行：1 3 3 1
第五行：1 4 6 4 1
第六行：1 5 10 10 5 1
输入格式
每个测试点有多组测试数据。
每个测试点第一行一个正整数T表示数据组数。
接下来T行每行两个正整数m，n, 表示一次询问。
这个三角的生成方式如下：
1. 第 i 行（i是正整数）有 i 个数。
2. 记第 i 行从左到右数第 j 个数为ai,j（ i, j 都是正整数），则
可见前6行的和为63 ,对 5 取模后结果为 3。前 2 行的和为 3,对 7 取模后结果为 3。
数据范围：
对于10%的数据，满足n≤5；
对于20%的数据，满足T=1，n≤50；
对于40%的数据，满足T≤10， n≤100；
对于60%的数据，满足n≤106；
对于90%的数据，满足n≤1018；
对于100%的数据，满足T≤103，m≤108，n≤101000，保证 m 为质数。
输出格式
共T行，每行一个正整数，表示答案。
输入样例 复制
3
5 6
7 2
2 998244353输出样例 复制
3
3
1