Background

WD is immersed in loops all day long and cannot break free.

Problem Description

One day, WD (a “juruo”, i.e., a newbie) wrote a very, very long for loop to solve a small problem:

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 took a look and said: WD, you idiot, isn’t this an easy problem? WD was completely confused, so he had to ask you to teach him.

Input Format

The first line contains an integer $T$, the number of test cases. Each of the following lines contains two integers $n, m$, representing the number of nested loops and the upper bound of each loop level, respectively.

Output Format

Output $T$ lines. Each line contains one integer, the answer.

2
2 9
10 14

55
1961256

Hint

$\text{subtask1}(23pts):~n,m\le 1,000,~1\le T\le 10,000$

$\text{subtask2}(35pts):~n,m\le 10^7,~1\le T\le 5$

$\text{subtask3}(42pts):~n,m\le 10^{18},~1\le T\le 100,000$

For Sample 1, you can just write some code and you will know the answer is 55 (just kidding).

Translated by ChatGPT 5