Mít và Xoài là các SV xuất sắc của thầy Luna. Sau khi dạy xong một tuyệt chiêu về phép đếm trong lập trình, thầy đã ra một bài rất tâm đắc cho Mít và Xoài làm. Hai bạn được cho bảng ô vuông kích thước ~n \times n~, mỗi ô được tô bởi một trong ba màu: xanh - đỏ - vàng sao cho không có hàng nào và không có cột nào được tô tất cả các ô bởi màu đỏ. Đánh số các hàng, cột theo thứ tự từ trái sang phải và dưới lên trên. Ban đầu có sẵn ~k~ ô được thầy Luna tô màu xanh hoặc vàng trước, cho biết danh sách tọa độ của chúng là thứ tự của hàng, cột của ô được tô. Nhiệm vụ của Mít và Xoài là đếm xem có tất cả bao nhiêu cách tô thỏa mãn điều kiện đề bài và kết quả có thể rất lớn nên lấy modulo ~10^9+7.~ Đã nhiều ngày nhưng các bạn vẫn chưa đếm xong, bạn có thể giúp hai bạn ấy được không?

Input

Dòng đầu tiên gồm hai số nguyên dương ~n,k~ trong đó ~1 \le n \le 10~ và ~0 \le k \le \min \{ n^2, 10 \}~. Các dòng tiếp theo mô tả tọa độ của các ô được tô màu trước với dạng ~x\, y \, z~ trong đó ~x,y~ là chỉ số hàng, cột, còn ~z~ là màu: ~z=1~ là xanh, ~z=2~ là vàng.

Output

Đáp số của bài toán.

Sample input

2 0

Sample output 1

56

Sample input 2

3 2
1 1 2
2 3 1

Sample output 2

2034