← 返回题目列表

Codeforces · 2127/F

F. 哈米德和 AghaBalaSar

中文机器翻译题面 查看原题

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$$$。

示例

输入
复制

8
2 5
3 4
4 6
5 10
6 23
100 100
142857 33333
200000 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$$$。