题目描述

注意：本题的时间限制为 6 秒，是默认的三倍。内存限制为 512MB，是默认的两倍。

Bessie 是一头饥饿的奶牛。每天晚餐时，如果谷仓里有干草，她就会吃掉一捆干草。农夫 John 不想让 Bessie 挨饿，所以有些天他会送来干草，这些干草会在早上（晚餐前）到达。特别地，在第 $d_i$ 天，农夫 John 会送来 $b_i$ 捆干草 $(1 \le d_i \le 10^{14}, 0 \le b_i \le 10^9)$。

处理 $U(1 \le U \le 10^5)$ 次更新如下：给定一对 $(d,b)$，更新第 $d$ 天到达的干草数量为 $b$。每次更新后，输出 Bessie 吃干草的所有天数之和，结果对 $10^9+7$ 取模。

输入格式

$U$，接下来是 $U$ 行，包含更新。

输出格式

每次更新后的和，对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

3
4 3
1 5
1 2

输出 #1

15
36
18

输入输出样例 #2

输入 #2

9
1 89
30 7
101 26
1 24
5 1
60 4
5 10
101 0
1 200

输出 #2

4005
4656
7607
3482
3507
3753
4058
1107
24531

说明/提示

示例 1 的解释

每次更新后的答案：

$4+5+6=15$
$1+2+3+4+5+6+7+8=36$
$1+2+4+5+6=18$

评分

• 输入 3：$U \le 5000$
• 输入 4-10：更新只会增加第 $d$ 天到达的干草数量。
• 输入 11-22：无额外约束。

题面翻译由 ChatGPT-4o 提供。