「PMOI-1」抽奖

活动奖池中共有 $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[0,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$ 金币。 1. 兑换 $114514$ 金币，获得 $A$ 体验卡。 1. 兑换 $114514$ 金币，获得 $B$ 体验卡。 1. 兑换 $114514$ 金币，获得 $A$ 永久道具。 1. 兑换 $114514$ 金币，获得 $B$ 永久道具。 1. 第一次获得 $A$ 体验卡，第二次获得 $A$ 体验卡。 1. 第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡。 1. 第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡。 1. 第一次获得 $B$ 体验卡，第二次获得 $B$ 体验卡。 1. 第一次获得 $A$ 体验卡，第二次获得 $A$ 体验卡，指定 $A$ 为永久道具。 1. 第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡，指定 $A$ 为永久道具。 1. 第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡，指定 $A$ 为永久道具。 1. 第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡，指定 $B$ 为永久道具。 1. 第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡，指定 $B$ 为永久道具。 1. 第一次获得 $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$。