您进入了第一个数据结构课程,您正在学习二分搜索。你听到教授大喊大叫为什么二分搜索在 $$$O(\log{n})$$$ 中有效。但您想看看是否可以找到更好的界限。
给定 已排序 大小为 $$$n$$$ 的数组 $$$a$$$ 和整数 $$$k$$$,将 $$$f(a, k, l, r)$$$ 定义为以下代码的结果:
function f(a, k, l, r):
if a does not contain k:
return 0
mid = floor((l+r) / 2)
if a[mid]==k:
return 1
else if a[mid]<k:
return 1+f(a, k, mid+1, r)
else:
return 1+f(a, k, l, mid-1)
给你两个整数 $$$n$$$ 和 $$$m$$$。定义一个数组 $$$a$$$ 好,如果:
- $$$|a|=n$$$ ($$$a$$$ 中有 $$$n$$$ 元素)。
- $$$1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq m$$$ (该数组是非递减的,下面以 $$$1$$$ 为界,上面以 $$$m$$$ 为界)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \leq n,m \leq 10^6$$$)。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$,所有测试用例的$$$m$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,在新行上输出请求的总和模 $$$676\,767\,677$$$。
示例
输入复制
73 33 43 54 34 5999967 9996715 876543
输出复制
26601155031593903683322710644
注意
在第一个测试用例中,一个好的数组 $$$a$$$ 是 $$$[2,2,3]$$$。这里,$$$f(a,1,1,n)=0$$$(因为$$$1$$$不存在于$$$a$$$中),$$$f(a,2,1,n)=1$$$,$$$f(a,3,1,n)=2$$$。所以这个好阵的贡献就是$$$0+1+2=3$$$。