0629 - 区間和剰余クエリ (Interval Remainder Query)

問題

JOIくんは、誕生日プレゼントとして、0 以上 M-1 以下の整数からなる、 長さ N の数列 A をもらいました。 JOIくんは数列 A に対して Q 個のクエリを処理しました。 i 個目のクエリは、A の L_i 番目から R_i 番目までの 要素の和を M で割った余りを求めるというもので、その答えは X_i でした。

ある日、JOIくんはうっかり数列 A を落として壊してしまいました。 しかしJOIくんは、整数 N ,M、クエリの情報、それらに対応する答えをすべて覚えています。 そこで、すべての記憶と矛盾しない数列 A としてありうるものが何通りあるかを求めることにしました。 あなたの仕事は、JOIくんの代わりにこれを求めるプログラムを作ることです。 ただし、答えは非常に大きくなることがあるので、10⁹+7 で割った余りを求めてください。 なお、JOIくんの記憶が間違っており、元の数列としてありうるものが存在しない場合もあります。 そのような場合は、0 を出力してください。

入力

N M Q
L1 R1 X1
L2 R2 X2
:
LQ RQ XQ

最初の一行には整数 N ,M ,Q が与えられる。

続く Q 行には、それぞれのクエリの情報が与えられる。

i 行目には、整数 L_i ,R_i ,X_i が与えられる。

出力

元の数列 A としてあり得るものが何通りあるかを 10⁹+7 で割った余りを出力してください。

制約

全ての入出力ケースについて以下を満たす。

• 1 ≦ N ≦ 10⁵
• 1 ≦ M ≦ 10⁹
• 1 ≦ Q ≦ 10⁵
• 1 ≦ L_i ≦ R_i ≦ N
• i != j の時、L_i != L_j または R_i != R_j の少なくとも一方が成り立つ。
• 0 ≦ X_i ≦ M-1

小課題

小課題1[20点]

以下の条件を満たす。

• 1 ≦ N ≦ 20
• 1 ≦ M ≦ 2
• 1 ≦ Q ≦ 50

小課題2[80点]

追加の制約はない。

---

入出力例

入力例1

4 2 4
1 4 1
1 2 0
3 4 1
2 3 0

出力例1

2

解説

条件を満たす数列は、(0,0,0,1) と (1,1,1,0) の二つです。このケースは小課題1の制約を満たします。

入力例2

6 4 5
1 2 0
1 4 3
6 6 2
3 4 1
3 5 0

出力例2

0