Problem11013--NC17507 - 发电

11013: NC17507 - 发电

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 512 MiB

SubmitSolved: 3Submit Num: 5StatisticsShowOff!

Description

HA实验是一个生产、提炼“神力水晶”的秘密军事基地，神力水晶可以让机器的工作效率成倍提升。
HA实验基地有 $n$ 台发电机，标号为 $1\sim n$，每台发电机的发电效率为 $1$。
为了满足基地的用电需求，HtBest会在某台发电机上镶嵌一个等级为i的神力水晶，该发电机的发电效率是镶嵌神力水晶之前的 $i$ 倍，一个发电机可以同时镶嵌多个神力水晶。
但是神力水晶有时还有别的用处，HtBest会拆掉某台发电机之前镶嵌上的一个神力水晶（设等级为 $i$），发电机效率降为拆掉神力水晶前的 $1/i$。
HtBest有时想知道第 $l$ 到 $r$ 台发电机的总发电效率为多少。

Input

第一行有 $2$ 个正整数 $n,m$，分别表示发电机数量和操作数。
接下来 $m$ 行，每行有 $3$ 个正整数，$x, y, z$。
$x=1$ 时，HtBest镶嵌为第 $y$ 台发电机镶嵌了一个等级为 $z$ 的神力水晶，
$x=2$ 时，HtBest为第 $y$ 台发电机拆掉了一个等级为 $z$ 的神力水晶，
$x=3$ 时，HtBest想知道 $[y,z]$ 的发电机效率的乘积。

Output

对于每个 $x=3$ 的操作，输出一行，表示 $[y,z]$ 的发电机的效率的乘积。
由于输出过大，你需要对输出结果模 $1000000007(10^9+7)$。

Constraints

$1 ≤ n, m ≤ 1,000,000$
$1 ≤$ 神力水晶等级 $≤ 100,000$

Sample 1 Input 

4 4
1 2 3
3 1 4
2 2 3
3 1 4

Sample 1 Output 

3
1
操作 1 之后，每台发电机效率：1 3 1 1
操作 3 之后，每台发电机效率：1 1 1 1

Sample 2 Input 

4 4
1 2 2
1 2 3
1 3 4
3 1 4

Sample 2 Output 

24
操作 1 之后，每台发电机效率：1 2 1 1
操作 2 之后，每台发电机效率：1 6 1 1
操作 3 之后，每台发电机效率：1 6 4 1

Sample 3 Input 

15 50
1 15 135
1 14 251
1 4 879
1 11 329
1 9 707
1 4 646
1 9 695
1 14 707
1 14 787
1 14 660
2 3 112
2 15 420
3 1 11
3 3 9
1 8 469
1 7 564
3 2 8
3 3 13
3 5 7
2 6 992
2 12 220
3 1 8
1 11 751
3 2 10
2 6 676
2 8 167
1 2 828
1 9 422
2 14 414
2 6 265
2 12 593
2 3 413
2 11 486
3 2 10
1 13 576
2 5 628
1 10 476
2 2 662
2 9 208
1 6 586
3 2 12
3 4 10
1 10 769
3 4 12
3 2 10
3 1 11
2 6 119
3 2 9
3 1 13
3 4 9

Sample 3 Output 

477894908
366194212
841081946
848599658
564
398025287
693777730
797395068
372324645
927238711
437928235
974942771
619101300
864066951
461902528
577005993

HINT

牛客网。

Source/Category

 
Submit