Trên lý thuyết, Ban tổ chức công bố hai số nguyên dương ~n~ và ~k~. Mỗi người chọn một dãy ~A = (a_1, a_2, \dots, a_n)~ gồm ~n~ số nguyên dương, sao cho ~1 \le a_i \le k~.

Sau đó Ban tổ chức công bố ~m~ nhóm, nhóm thứ ~j~ gồm ba số ~L_j, R_j, X_j~ và yêu cầu:

~\max{a_i \mid i = L_j \dots R_j} = X_j \quad (j = 1 \dots m)~

Hãy tính số lượng dãy ~A~ thỏa mãn tất cả điều kiện trên, lấy modulo ~10^9+7~.

Yêu cầu

Tính số lượng dãy ~A~ độ dài ~n~, với ~1 \le a_i \le k~, sao cho với mọi ~j~:

• ~\max(a_{L_j}, a_{L_j+1}, \dots, a_{R_j}) = X_j~.

In kết quả theo modulo ~10^9+7~.

Dữ liệu

• Dòng 1: ba số nguyên ~n, m, k~ (~1 \le n, m \le 10^5~, ~1 \le k \le 10^9~).
• ~m~ dòng tiếp theo: mỗi dòng chứa ~L_j, R_j, X_j~ (~1 \le L_j \le R_j \le n~, ~1 \le X_j \le k~).

Kết quả

In ra một số nguyên — số lượng dãy thỏa mãn, modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

5 3 5
1 3 2
1 2 1
1 5 5

Output

9

Ràng buộc

• ~1 \le n, m \le 10^5~
• ~1 \le k \le 10^9~
• ~1 \le L_j \le R_j \le n~
• ~1 \le X_j \le k~