题目描述

题目译自 USACO 2023 February Contest, Platinum Problem 1. Hungry Cow

Bessie 是一头很饿的奶牛。每天晚饭如果谷仓里有干草的话，她会吃一捆干草。FJ 不想让 Bessie 饿着，所以在一些天他会送一些干草，这些干草会早上送到（在晚饭之前）。具体来说，在第 $d_i\ (1\le d_i\le 10^{14})$ 天，FJ 会送 $b_i\ (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$ 取模后的结果。

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

数据范围与提示

• 第 3 组数据：$U\le 5\ 000$
• 4-10 组数据：更新只会增加第 $d$ 天送到的干草
• 11-22 组数据：无附加限制