Description

There are $n$ types of items in the event prize pool, and dead_X has $m$ redemption coupons. One coupon can be exchanged for one lottery chance or $114514$ coins.

dead_X decides to use some coupons for the lottery, and exchange the remaining coupons for coins.

In one lottery chance, dead_X will obtain, with equal probability, a $1919810$-second trial card of one item from the prize pool.

Because dead_X bought a VIP card in the event, after all lotteries are finished, he may choose one type of trial card obtained from the lotteries, submit all trial cards of that type, and receive the corresponding type of permanent item.

Note that dead_X may choose not to use this feature, but he cannot use it more than once.

dead_X, who has trouble making choices, wants to know how many possible event outcomes there are.

Two event outcomes are different if and only if the coins obtained are different, or the trial card obtained in any lottery is different (i.e., the sequence of drawn trial cards is different), or the permanent item obtained is different.

Note that the lottery only gives trial cards. The final chosen permanent item is unrelated to which draw each trial card came from.

Update 2023.11.16: The problem setter could not stand the statement written years ago, so here is a formal statement.

Define the weight of a sequence as the number of distinct elements in it $+1$. For example, the weight of $[1,9,2,6,8,1,7]$ is $7$.

For all integer sequences whose length $\in[0,m]$ and each number $\in [1,n]$, compute the sum of their weights modulo $10^9+7$.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, input two positive integers $n,m$, representing the number of item types and the number of redemption coupons.

Output Format

Output $T$ lines in total. Each line contains one positive integer, the number of outcomes modulo $10^9+7$.

5
2 1
2 2
3 3
114 514
1919810 7872754

5
15
115
338602801
30498159

Hint

[Sample Explanation]

The following are all possible outcomes for the second test case:

Assume the two items are $A$ and $B$.

1. Exchange for $229028$ coins.
2. Exchange for $114514$ coins, obtain an $A$ trial card.
3. Exchange for $114514$ coins, obtain a $B$ trial card.
4. Exchange for $114514$ coins, obtain an $A$ permanent item.
5. Exchange for $114514$ coins, obtain a $B$ permanent item.
6. First obtain an $A$ trial card, second obtain an $A$ trial card.
7. First obtain an $A$ trial card, second obtain a $B$ trial card.
8. First obtain a $B$ trial card, second obtain an $A$ trial card.
9. First obtain a $B$ trial card, second obtain a $B$ trial card.
10. First obtain an $A$ trial card, second obtain an $A$ trial card, designate $A$ as the permanent item.
11. First obtain an $A$ trial card, second obtain a $B$ trial card, designate $A$ as the permanent item.
12. First obtain a $B$ trial card, second obtain an $A$ trial card, designate $A$ as the permanent item.
13. First obtain an $A$ trial card, second obtain a $B$ trial card, designate $B$ as the permanent item.
14. First obtain a $B$ trial card, second obtain an $A$ trial card, designate $B$ as the permanent item.
15. First obtain a $B$ trial card, second obtain a $B$ trial card, designate $B$ as the permanent item.

[Constraints]

• Subtask 1 (10 pts): $n,m\leq5,T\le25$.
• Subtask 2 (10 pts): $n=1$.
• Subtask 3 (10 pts): $m=1$.
• Subtask 4 (20 pts): $n,m\leq1000,T\leq 5$.
• Subtask 5 (20 pts): $\sum m\leq10^6$.
• Subtask 6 (30 pts): no special restrictions.

For $100\%$ of the testdata, $1\le n,m\leq 10^9$ and $1\le T\leq 10^5$.

Translated by ChatGPT 5