WD与循环
题目背景
WD整日沉浸在循环中，无法自拔……
题目描述
这天，WD蒟蒻为了解决一个小问题写了个很长很长的for循环：
```cpp
int cnt = 0;
for (int a_1 = 0; a_1 <= m; a_1++) {
for (int a_2 = 0; a_1 + a_2 <= m; a_2++) {
...
for (int a_n = 0; a_1 + a_2 + ... + a_n <= m; a_n++) {
cnt = (cnt + 1) % 19491001;
}
}
}
printf("%d\n", cnt);
```
CX过来看了一眼，说：**WD你个笨蛋，这道题不是SB题吗？**WD一脸懵逼，只好请你来教教他啦……
输入输出格式
输入格式
第一行一个数$T$，表示数据组数。接下来每行两个数$n,m$，分别表示循环重数和每层循环的上界。
输出格式
共$T$行，每行一个数表示答案。
输入输出样例
输入样例 #1
2
2 9
10 14输出样例 #1
55
1961256说明
$subtask1(23pts):~n,m\le 1,000,~1\le T\le 10,000$
$subtask2(35pts):~n,m\le 10^7,~1\le T\le 5$
$subtask3(42pts):~n,m\le 10^{18},~1\le T\le 100,000$
对于样例1，写个代码就知道答案是55了（大雾）。