题目描述

平面上有n个珠子排成一排， 每个珠子初始颜色为0，你要对他们进行m次染色。

每次你选定l和r，然后把[l,r]之间的珠子染成编号c的颜色，每个珠子的最终颜色为它曾经染过的编号最大的颜色。

请你写个程序统计每个珠子最终的颜色。

输入格式

第一行两个数n，m，表示珠子个数和染色的次数；

接下来m行，每行三个数l,r,c如题意所示

输出格式

由于数据较大，为了减少输出所用的不必要的时间，请采取以下方法输出：

假如a[i]为第i个珠子的最终颜色

ans=0;

for (int i=1;i<=n;i++) ans=(ans*1200007+a[i]) % 999911659;

cout<<ans<<endl;

注意用long long保存相关变量，防止运算过程中越界

样例数据

input

3 2

1 2 1

2 2 2

output

146411103

数据规模与约定

保证$n,m \leq 2\times 10^6$。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$