Snuke bermain dengan keping berikut (keping ini digunakan dalam permainan bernama TRAX):

Snuke ingin mengisi sebuah petak berukuran $H \times W$ dengan keping-keping ini. Di setiap sel petak, ia meletakkan sebuah keping dalam salah satu dari empat orientasi:

Orientasi-orientasi ini diberi nomor 1 hingga 4 seperti pada gambar di atas.

Penempatan keping harus memenuhi batasan berikut:

• Busur merah tidak boleh bersentuhan dengan busur putih.
• Petak tidak boleh mengandung siklus (lihat contoh di bawah).
• Untuk setiap $i$ ($1 \le i \le N$), orientasi keping pada sel di baris ke-$R_i$ dari atas dan kolom ke-$C_i$ dari kiri haruslah $D_i$.

Sebagai contoh, gambar berikut menunjukkan dua penempatan keping yang tidak valid. Penempatan di kiri mengandung siklus putih, dan penempatan di kanan mengandung siklus merah serta siklus putih yang besar.

Hitung jumlah penempatan yang valid, modulo $10^9+7$.

Masukan

$$ \begin{gathered} H\quad W\\ N\\ R_1\quad C_1\quad D_1\\ \vdots\\ R_N\quad C_N\quad D_N \end{gathered} $$

• $1 \le H,W \le 10^5$
• $0 \le N \le 10^5$
• $1 \le R_i \le H$
• $1 \le C_i \le W$
• $1 \le D_i \le 4$
• Pasangan $(R_i,C_i)$ berbeda satu sama lain.

Keluaran

Cetak jumlah penempatan yang valid, modulo $10^9+7$.

Contoh

Masukan 1

2 2
1
1 1 4

Keluaran 1

4

Masukan 2

2 10
2
1 1 1
1 2 1

Keluaran 2

0

Masukan 3

2015 1114
0

Keluaran 3

711460824

Masukan 4

2 2
2
1 1 1
2 2 3

Keluaran 4

0

Masukan 5

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

Keluaran 5

12

Masukan 6

5 6
2
3 3 4
3 4 2

Keluaran 6

39

Catatan

Untuk contoh 1, berikut adalah empat penempatan yang valid: