Ivan is designing a template problem for a high school informatics competition. In this problem, a sequence of numbers $S = a_1, a_2, \dots, a_n$ is given, where $0 \le a_j < H$, along with $m$ queries of the form $x_j, y_j$ where $1 \le x_j \le y_j \le n$. The answer to the $j$-th query is the maximum of the numbers in the sequence $S$ at positions between $x_j$ and $y_j$ inclusive: $z_j = \max(a_{x_j}, a_{x_j+1}, \dots, a_{y_j})$.

Ivan created an excellent test case for this problem, but he lost the original sequence $S$. You are given the length of the original sequence $n$, the constraint on the size of the sequence elements $H$, and $m$ queries $x_j, y_j$ along with their corresponding answers $z_j$. A sequence $S$ of length $n$ is good if it consists of numbers between $0$ and $H - 1$ inclusive, and every $z_j$ is the correct answer for the corresponding query $x_j, y_j$. Determine the number of good sequences $S$ modulo $10^9 + 7$.

Input

The first line contains the natural numbers $n$, $m$, and $H$ — the length of the sequence, the number of queries, and the constraint on the size of the sequence elements. In the $j$-th of the following $m$ lines, there are three integers $x_j$, $y_j$, and $z_j$ ($1 \le x_j \le y_j \le n$, $0 \le z_j < H$) — the $j$-th query and its answer.

Output

Print a single number — the required number of good sequences modulo $10^9 + 7$.

Subtasks

In all subtasks, $1 \le m, H \le 10^6$.

Examples

Input 1

3 2 3
1 2 1
2 2 0

Output 1

3

Input 2

7 10 3
1 3 1
3 4 1
3 6 2
4 5 2
1 1 1
1 2 1
3 3 0
1 1 1
3 3 0
3 6 2

Output 2

18

Note

Explanation of the first example: Due to the second query, the element $a_2$ must be $0$, and therefore, due to the first query, the element $a_1$ must be $1$. The element $a_3$ can be any non-negative integer less than $H = 3$. Thus, all good sequences $S$ are $(1, 0, 0)$, $(1, 0, 1)$, and $(1, 0, 2)$.