Find Maximum Total Amount (SDE I, Fungible :)

Bags are numbered starting from 1. Within each of the non-overlapping closed intervals [l,r], every bag holds amount v, and bags not listed hold 0. Choose exactly k consecutive bags, first maximize the real amount, then return that maximum modulo 1000000007.

输入格式

The first line contains n k, followed by n lines l r v. This site sets 1≤n≤100000, 1≤l≤r≤10^9, 1≤k≤10^9, 1≤v≤10^9; the intervals do not overlap, and the input may be unordered.

输出格式

Output a single integer answer.

样例 1

输入：

4 5
1 4 2
6 6 5
7 7 7
9 10 1

输出：

16

样例 2

输入：

1 10
2 3 4

输出：

8

样例 3

输入：

2 2
1 2 500000004
4 4 2

输出：

1

样例说明

Example 1: choose 3..7 for an amount of 2+2+0+5+7=16. Example 2: a length of 10 can cover two bags of 4 each, giving 8. Example 3: choose the first two bags; their real amount 1000000008 is greater than any other window, so choose it first and then take the modulo, giving 1.