問題文

トール君は、数列が大好きな男の子です。

トール君がいつものようにリビングで数列を愛でていると、テレビから「多様性」という言葉が聞こえてきました。

それを聞いたトール君は、自分が持っている数列にも多様性をもたせたいと思い、以下の条件をすべて満たすような N 要素の整数からなる数列 a_1, ..., a_N を作ることにしました。

• a_{l_i}, a_{l_i + 1}, ..., a_{r_i} の中に b_i とは異なる値が少なくとも1つ存在する。(1 \leq i \leq M)
• すべての要素の値は 1 以上 S 以下である。

トール君はこれらの条件を満たす数列が何通りあるかが気になりましたが、自力で数えるのは難しいことに気が付きました。

トール君の代わりに、あり得る数列の個数を求めてあげましょう。答えは非常に大きくなりうるので、10^9 + 7 で割ったあまりを出力してください。

制約

• 入力はすべて整数で与えられる。
• 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
• (l_i, r_i, b_i) の組はすべて異なる。

入力例1

3 2 2
1 2 1
2 3 2

出力例1

4

満たすべき条件は、以下の 3 つです。

• a_1, a_2 のうち少なくとも 1 つは 1 以外の整数である。
• a_2, a_3 のうち少なくとも 1 つは 2 以外の整数である。
• 数列の要素の値はすべて 1 以上 2 以下である。

これを満たす数列は、(1, 2, 1), (2, 1, 1), (2, 1, 2), (2, 2, 1) の 4 つ存在します。

入力例2

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

出力例2

65364

入力例3

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

出力例3

7984

入力例4

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

出力例4

145394311

入力例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

出力例5

3439