Bessie 是一头饥饿的奶牛。每天晚餐时，如果谷仓里有干草捆，她就会吃掉一个。农夫约翰不想让 Bessie 挨饿，所以他会在某些日子运送干草捆，这些干草捆会在当天早上（晚餐前）送达。具体来说，在第 $d_i$ 天，农夫约翰会送来 $b_i$ 个干草捆（$1\leq d_i \leq 10^{14}$，$0\leq b_i \leq 10^9$）。

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

样例

输入格式 1

3
4 3
1 5
1 2

输出格式 1

15
36
18

说明

每次更新后的答案：

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

输入格式 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

SCORING

• 输入 3：$U\le 5000$
• 输入 4-10：更新操作仅会增加第 $d$ 天送达的干草捆数量。
• 输入 11-22：无额外限制。

题目来源：Brandon Wang 和 Benjamin Qi