Boboniu đi trên đồ thị

Cho một đồ thị có hướng gồm $n$ đỉnh và $m$ cạnh. Bậc ra của mỗi đỉnh không vượt quá $k$. Mỗi cạnh có một trọng số nguyên trong đoạn $[1,m]$, và không có hai cạnh nào có cùng trọng số.

Một bộ luật đi được biểu diễn bởi bộ $k$ số nguyên $(c_1,c_2,\dots ,c_k)$, trong đó $1\le c_i\le i$ với mọi $i$ từ $1$ đến $k$. Khi đứng tại một đỉnh $u$ có bậc ra bằng $i$, ta sẽ đi tiếp theo cạnh có trọng số nhỏ thứ $c_i$ trong tất cả các cạnh xuất phát từ $u$.

Hãy đếm số bộ $(c_1,c_2,\dots ,c_k)$ thỏa mãn cả hai điều kiện sau:

• $1\le c_i\le i$ với mọi $i$ từ $1$ đến $k$.
• Xuất phát từ bất kỳ đỉnh $u$ nào, đi theo bộ luật ta luôn có thể quay trở về $u$ sau một số hữu hạn bước.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$ và $k$.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$, $w$ — mô tả một cạnh có hướng từ $u$ đến $v$ với trọng số $w$.

Dữ liệu đảm bảo không có khuyên hay cạnh bội, mỗi đỉnh có ít nhất một cạnh đi ra, bậc ra của mỗi đỉnh không vượt quá $k$, và không có hai cạnh trùng trọng số.

Dữ liệu ra

Một số nguyên duy nhất — số bộ $(c_1,c_2,\dots ,c_k)$ thỏa mãn.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $2\le m\le min(2·{10}^5,n(n-1))$
• $1\le k\le 9$
• $1\le u,v\le n$, $u\ne v$, $1\le w\le m$

Ví dụ