题目描述

Note: The time limit for this problem is 6s, three times the default. The memory limit for this problem is 512MB, twice the default.

Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day $d_i$, Farmer John sends a delivery of $b_i$ haybales $(1 \le d_i \le 10^{14}, 0 \le b_i \le 10^9)$.

Process $U(1 \le U \le 10^5)$ updates as follows: Given a pair $(d,b)$, update the number of haybales arriving on day $d$ to $b$. After each update, output the sum of all days on which Bessie eats haybales modulo $10^9+7$.

输入格式

$U$, followed by $U$ lines containing the updates.

输出格式

The sum after each update modulo $10^9+7$.

题目大意

Bessie 很饿，每天晚饭如果有干草就会吃 $1$ 份，没有就不吃，初始没有干草。

每天早上 Farmer John 会给它送若干干草，设第 $k$ 天送 $a_k$ 份干草，初始时 $a_k=0$，表示该天不送干草。

$q$ 次操作，每次给出 $x,y$，表示将 $a_x$ 改成 $y$，请将在此时 Bessie 有干草吃的日期编号求和并输出。对 $10^9+7$ 取模。

操作间互不独立。

$1\le q\le10^5$，$1\le x\le10^{14}$，$0\le y\le10^9$。

3
4 3
1 5
1 2

15
36
18

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

4005
4656
7607
3482
3507
3753
4058
1107
24531

提示

Explanation for Sample 1

Answers after each update:

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

SCORING

• Input $3$: $U \le 5000$
• Inputs $4-10$: Updates only increase the number of haybales arriving on day $d$.
• Inputs 11-22: No additional constraints.