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

時間制限 1 秒 / メモリ制限 256 MB / 得点 100 / x 0 /


TLE
1sec
MLE
256MB
得点
100

問題

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

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

入力

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

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

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

i 行目には、整数 Li ,Ri ,Xi が与えられる。

出力

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

制約

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

  • 1 ≦ N ≦ 105
  • 1 ≦ M ≦ 109
  • 1 ≦ Q ≦ 105
  • 1 ≦ Li ≦ Ri ≦ N
  • i != j の時、Li != Lj または Ri != Rj の少なくとも一方が成り立つ。
  • 0 ≦ Xi ≦ 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