Cho ~3~ số nguyên dương ~N, K, M~ và ~M~ bộ tham số: ~(l_1, r_1, v_1), (l_2, r_2, v_2), ..., (l_M, r_M, v_M)~.

Đếm số lượng dãy ~A~ khác nhau, gồm ~N~ phần tử số nguyên thỏa mãn:

• ~0 \le A[j] < 2^K~ với mọi ~1 \le j \le N~.
• Với mỗi ~1 \le i \le M~ thì ~A[l_i] \text{ AND } A[l_i+1] \text{ AND } \dots \text{ AND } A[r_i] = v_i~. Trong đó ~\&~ là ký hiệu toán tử ~AND~.

Input

• Dòng đầu tiên gồm ba số nguyên ~N, K, M~ (~N \le 10^5, K \le 30, M \le 10^5~).
• ~M~ dòng tiếp theo, dòng thứ ~i~ là bộ ba số ~l_i, r_i~ và ~v_i~ (~1 \le l_i \le r_i \le N; 0 \le v_i < 2^K~).

Output

• Gồm một dòng duy nhất là kết quả bài toán khi lấy phần dư khi chia cho ~1000000007~. Hai dãy ~A~ và ~B~ được coi là khác nhau nếu tồn tại một vị trí ~i~ (~1 \le i \le N~) mà ~A_i \ne B_i~.

Sample Input 1

4 2 2
1 3 2
3 4 1

Sample Output 1

3

Giải thích ví dụ

Có ~3~ dãy thỏa mãn là ~\{2, 2, 3, 1\}, \{2, 3, 3, 1\}, \{3, 2, 3, 1\}~.

Subtasks