Đếm dãy

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),\dots ,(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]\&A[l_i+1]\&\dots \&A[r_i]=v_i$.

Trong đó $\&$ là kí hiệu toán tử $AND$ (AND theo bit).

Dữ liệu vào

• 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$).

Dữ liệu ra

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$.

Ràng buộc

• $1\le N\le {10}^5$, $1\le K\le 30$, $1\le M\le {10}^5$.
• $1\le l_i\le r_i\le N$, $0\le v_i<2^K$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($15\%$ số test): $M,N\le 10$; $K\le 2$.
• Subtask 2 ($15\%$ số test): $M,N\le 1000$ và $r_i<l_{i+1}$ với mọi $1\le i<M$.
• Subtask 3 ($20\%$ số test): $K=1$; $N,M\le 1000$.
• Subtask 4 ($20\%$ số test): $M,N\le 1000$.
• Subtask 5 ($30\%$ số test): không có điều kiện gì thêm.

Ví dụ