Counting Valid RMQ Sequences

You are given an integer sequence a₁, a₂, …, a_n whose values lie in the range \([0,h)\) (i.e. each \(a_i\) is an integer satisfying \(0\le a_i\le h-1\)).

There are m queries. The i-th query gives two indices \(l_i\) and \(r_i\) (1-indexed) along with an answer \(v_i\). The answer means that in the interval \([l_i, r_i]\) the maximum element is exactly \(v_i\); in other words,

[ \max_{l_i\le k\le r_i} {a_k} = v_i. ]

Your task is: given n, m and \(h\), and the m queries (each with its corresponding answer), count how many sequences \(a\) satisfy all the conditions. Print the answer modulo \(10^9+7\).

Note: For any query \([l, r]\) with answer \(v\), the condition means that for every index \(k\) with \(l\le k\le r\) we must have \(a_k\le v\) and at least one index in \([l, r]\) must receive the value \(v\). All formulas above are given in \(\LaTeX\) format.

inputFormat

The first line contains three integers: \(n\) \(m\) \(h\).

The next \(m\) lines each contain three integers: \(l_i\), \(r_i\) and \(v_i\) representing a query. It is guaranteed that \(1\le l_i\le r_i\le n\) and \(0\le v_i<h\).

outputFormat

Output one integer: the number of valid sequences \(a\) that satisfy every query condition, taken modulo \(10^9+7\).

sample

3 1 5
1 3 3

37