Lottery

Deep underground, in Gru's villainous laboratory, live countless minions. To liven up the lives of the yellow creatures, Gru decided to hold a lottery every month. The lottery works as follows. Each minion is given an array of length n whose elements are all positive integers not exceeding k.

Gru then announces a list of m triples of numbers lᵢ, rᵢ, xᵢ. The minions who win the lottery are those whose array has the following property: for each i, considering the elements of the array with indices from lᵢ to rᵢ, the maximum among these elements in the minion's array is the number xᵢ.

Gru became curious how many minions will come to him for prizes. Help him!

Every possible array is considered to have gone to exactly one minion. Since the answer can be quite large, output the remainder of dividing the sought number of winners by 109 + 7.

The first line contains three integers n, m, k (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000, 1 ≤ k ≤ 109): the size of the arrays, the number of queries, and the maximum number that can appear in the array. The next m lines contain three numbers each, lᵢ, rᵢ, xᵢ (1 ≤ l ≤ r ≤ n, 0 ≤ xᵢ ≤ k): Gru's list of triples.

In the single line of the output file, output the remainder of dividing the number of winning minions by 109 + 7.