Problem Description

Toru is a boy who loves sequences.

As Toru was admiring sequences in the living room, he heard the word "diversity" from the TV.

Inspired by this, Toru decided to create an integer sequence of $ N $ elements $ a_1, ..., a_N $ that satisfies all the following conditions:

• There is at least one value different from $ b_i $ in the subsequence $ a_{l_i}, a_{l_i + 1}, ..., a_{r_i} $ for each $1 \leq i \leq M$.
• All elements are between $ 1 $ and $ S $ inclusive.

Toru wondered how many such sequences exist, but he realized that counting them by himself would be difficult.

Let's help Toru by finding the number of possible sequences. Since the answer can be very large, output the result modulo $ 10^9 + 7 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ S $ $ l_1 $ $ r_1 $ $ b_1 $ $ l_2 $ $ r_2 $ $ b_2 $ $ : $ $ l_M $ $ r_M $ $ b_M $

Output Format

Output the total number of possible sequences modulo $ 10^9 + 7 $.

Sample Input and Output

Sample Input #1

3 2 2
1 2 1
2 3 2

Sample Output #1

4

Sample Input #2

8 3 4
1 5 1
2 6 1
4 8 1

Sample Output #2

65364

Sample Input #3

7 6 4
1 5 1
3 6 3
2 2 4
5 7 4
4 7 2
2 2 3

Sample Output #3

7984

Sample Input #4

5 3 52657
1 2 1
4 5 1
1 5 1

Sample Output #4

145394311

Sample Input #5

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

Sample Output #5

3439

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq S \leq 10^5$
• $1 \leq l_i \leq r_i \leq N$
• $1 \leq b_i \leq S$
• All pairs $ (l_i, r_i, b_i) $ are distinct.

Sample Explanation 1

The conditions to be satisfied are:
- At least one of $ a_1, a_2 $ is an integer other than $ 1 $.
- At least one of $ a_2, a_3 $ is an integer other than $ 2 $.
- All elements of the sequence are between $ 1 $ and $ 2 $ inclusive.

The sequences that satisfy these conditions are $ (1, 2, 1) $, $ (2, 1, 1) $, $ (2, 1, 2) $, and $ (2, 2, 1) $, totaling $ 4 $ sequences.

见题面 Input 部分

见题面 Output 部分