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ả:

• 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 Input 1

2 1 5
1 2 3

Sample Output 1

1

Sample Input 2

3 2 6
1 2 3
3 1 2

Sample Output 2

2