AT_kupc2018_h カラフル数列

[problemUrl]: https://atcoder.jp/contests/kupc2018/tasks/kupc2018_h トール君は、数列が大好きな男の子です。 トール君がいつものようにリビングで数列を愛でていると、テレビから「多様性」という言葉が聞こえてきました。 それを聞いたトール君は、自分が持っている数列にも多様性をもたせたいと思い、以下の条件をすべて満たすような $ 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 $ で割ったあまりを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ S $ $ l_1 $ $ r_1 $ $ b_1 $ $ l_2 $ $ r_2 $ $ b_2 $ $ : $ $ l_M $ $ r_M $ $ b_M $

数列としてありえるものの総数を $ 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) $ の組はすべて異なる。 ### Sample Explanation 1 満たすべき条件は、以下の $ 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 $ つ存在します。