Hamid 为 a+b 问题编写了 $$$3014$$$ 行代码,并将其中 $$$10$$$ 行交给了 Hamed;然后哈米德想到了以下问题。
给你两个整数 $$$n$$$ 和 $$$m$$$。
调用数组 $$$a_1,a_2,\ldots,a_n$$$ 蛇 当且仅当满足以下所有条件时:
- $$$a$$$中的所有元素都是$$$0$$$和$$$m$$$之间的整数;
- $$$a_1 + a_2 + \cdots + a_n = m$$$;
- $$$a_n=\max\left([a_1, a_2, \ldots, a_n]\right)$$$。
我们定义 $$$f(a)$$$ 如下伪代码所示:
function f(array a):
pos := 1
res := 0
let nxt[x] be an array such that nxt[x] is the smallest index y such that
y > x and a[y] > a[x],
or undefined if no such y exists
while pos < n:
if a[pos] < a[n]:
res += a[nxt[pos]] - a[pos]
pos := nxt[pos]
else:
pos += 1
return res
求 $$$f(a)$$$ 的总和 蛇 数组 $$$a_1,a_2,\ldots,a_n$$$,模 $$$10^9+7$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$) — a 的长度 蛇 数组以及 a 中所有元素的总和 蛇 数组。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - $$$f(a)$$$ 的总和 蛇 数组 $$$a_1,a_2,\ldots,a_n$$$,模 $$$10^9+7$$$。
示例
输入复制
82 53 44 65 106 23100 100142857 33333200000 0
输出复制
9 14 76 985 142112 771227753 865580631 0
注意
在第一个测试用例中,有三个 蛇 数组:
- $$$f([0, 5]) = 5$$$;
- $$$f([1, 4]) = 3$$$;
- $$$f([2, 3]) = 1$$$。
因此,答案是$$$5+3+1=9$$$。
在第二个测试用例中,有六个 蛇 数组:
- $$$f([0, 0, 4]) = 4$$$;
- $$$f([0, 1, 3]) = 3$$$;
- $$$f([1, 0, 3]) = 2$$$;
- $$$f([1, 1, 2]) = 1$$$;
- $$$f([0, 2, 2]) = 2$$$;
- $$$f([2, 0, 2]) = 2$$$。
因此,答案是$$$4+3+2+1+2+2=14$$$。
在第五个测试用例中,可能的 蛇 数组是:
- $$$f([3, 1, 4, 1, 5, 9]) = 6$$$。