题目描述

活动奖池中共有 $n$ 种道具，dead_X 有 $m$ 张兑奖券。一张兑奖券可以兑换成一次抽奖机会或 $114514$ 金币。

dead_X 决定将一部分兑奖券拿来抽奖，并将剩下的兑奖券兑换成金币。

在一次抽奖机会中，dead_X 会等概率得到所有奖池中一款道具的 $1919810$ 秒体验卡。

由于 dead_X 在活动中买了 VIP 卡，他可以在所有抽奖结束后选择一款抽奖得到的体验卡，将所有这种类型的体验卡上交，并得到对应种类的永久道具。

注意，dead_X 可以不使用这个功能，但是不可以使用多于一次。

有选择困难症的 dead_X 想知道，有多少种可能的活动结果。

两种活动结果不同，当且仅当 dead_X 获得的金币不同，或者在任何一次抽奖中获得的体验卡不同（即抽到体验卡形成的序列不同），或者获得的永久道具不同。

注意，抽奖中获得的都是体验卡，最后选择的永久道具和体验卡在哪一次抽出没有关系。

Update 2023.11.16：出题人看自己好几年前写的题面绷不住了，补一份形式化题面。

定义一个序列的权值是其不同元素个数 $+1$，例如 $[1,9,2,6,8,1,7]$ 的权值是 $7$。

对于所有长度 $\in[1,m]$，每个数 $\in [1,n]$ 的整数序列，求其权值和对 $10^9+7$ 取模的值。

输入格式

本题有多组数据。

第一行一个整数 $T$，代表数据组数。

对于每组数据，输入两个正整数 $n,m$，分别表示道具的种数和兑奖券的张数。

输出格式

输出共 $T$ 行，每行输出一个正整数，代表方案数对 $10^9+7$ 取模的值。

5
2 1
2 2
3 3
114 514
1919810 7872754

5
15
115
338602801
30498159

提示

【样例解释】

以下为第二组测试数据所有可能的方案：

假设两种物品分别为 $A$ 和 $B$。

1. 兑换 $229028$ 金币。
2. 兑换 $114514$ 金币，获得 $A$ 体验卡。
3. 兑换 $114514$ 金币，获得 $B$ 体验卡。
4. 兑换 $114514$ 金币，获得 $A$ 永久道具。
5. 兑换 $114514$ 金币，获得 $B$ 永久道具。
6. 第一次获得 $A$ 体验卡，第二次获得 $A$ 体验卡。
7. 第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡。
8. 第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡。
9. 第一次获得 $B$ 体验卡，第二次获得 $B$ 体验卡。
10. 第一次获得 $A$ 体验卡，第二次获得 $A$ 体验卡，指定 $A$ 为永久道具。
11. 第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡，指定 $A$ 为永久道具。
12. 第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡，指定 $A$ 为永久道具。
13. 第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡，指定 $B$ 为永久道具。
14. 第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡，指定 $B$ 为永久道具。
15. 第一次获得 $B$ 体验卡，第二次获得 $B$ 体验卡，指定 $B$ 为永久道具。

【数据范围】

• Subtask1（10pts）：$n,m\leq5,T\le25$；
• Subtask2（10pts）：$n=1$；
• Subtask3（10pts）：$m=1$；
• Subtask4（20pts）：$n,m\leq1000,T\leq 5$；
• Subtask5（20pts）：$\sum m\leq10^6$；
• Subtask6（30pts）：无特殊限制。

对于 $100\%$ 的数据满足，$1\le n,m\leq 10^9$，$1\le T\leq 10^5$。