Cho ba số nguyên \(n\), \(m\), \(x\). Bạn cần đếm số lượng dãy \(a_1, a_2, \dots, a_n\) thoả mãn:

• Các phần tử \(a_i\) có giá trị thuộc \([1, x]\).
• Dãy thoả \(m\) điều kiện được biểu diễn bởi bộ ba phần tử \((i, j, g)\) cho biết \(GCD(a_i, a_j) = g\).

Input

• Dòng đầu tiên gồm ba số nguyên dương \(n\), \(m\), \(x\) (\(3 \le n \le 9, 0 \le m \le n, 3 \le x \le 12\)).
• \(m\) dòng tiếp theo, mỗi dòng gồm ba sốn nguyên dương \(i\), \(j\), \(g\) (\(1 \le i, j \le n \; và \; i \ne j, 2 \le g \le x\)).

Output

Một số nguyên duy nhất là số lượng dãy \(a_1, a_2, \dots, a_n\) thoả.

Scoring

• \(20\%\) test có \(n, m, x \le 7\).
• \(20\%\) test khác có \(|i - j| = 1\) với mọi truy vấn.
• \(60\%\) số test còn lại không có ràng buộc gì thêm.

Sample Test

Input:

2 1 5
1 2 3

Output:

1

Input:

3 2 6
1 2 3
3 1 2

Output:

2