2080 - QMaxGCD

wlxsq有一个n个元素的数列A={a_1,a_2,...,a_n},初始值均为1,现在wlxsq有q次操作,每次操作对一个指定的区间[l,r]中的每一个数乘上cntx
q次操作之后,wlxsq想知道,这n个数的最大公约数是多少。你能帮帮wlxsq吗?

输入

第一行输入两个整数nq
接下来q行,每行输入4个整数l,r,cnt,x.表示对区间[l,r]内的每一个数都累乘上cntx

输出

输出n个数的最大公约数,结果对1e9+7取模

样例

输入

5 3
1 3 1 2
3 5 1 2
1 5 1 3

输出

6

输入

6 3
1 2 1 2
5 6 1 2
1 6 1 2

输出

2

提示

数据规模 
1<=n<=10^6,1<=q<=10^5,cntint类型数据,x在集合{2,3}中取数。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题