Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Boboniu Walks on Graph

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBoboniu has a directed graph with $$$n$$$ vertices and $$$m$$$ edges.

The out-degree of each vertex is at most $$$k$$$.

Each edge has an integer weight between $$$1$$$ and $$$m$$$. No two edges have equal weights.

Boboniu likes to walk on the graph with some specific rules, which is represented by a tuple $$$(c_1,c_2,\ldots,c_k)$$$. If he now stands on a vertex $$$u$$$ with out-degree $$$i$$$, then he will go to the next vertex by the edge with the $$$c_i$$$-th $$$(1\le c_i\le i)$$$ smallest weight among all edges outgoing from $$$u$$$.

Now Boboniu asks you to calculate the number of tuples $$$(c_1,c_2,\ldots,c_k)$$$ such that

- $$$1\le c_i\le i$$$ for all $$$i$$$ ($$$1\le i\le k$$$).
- Starting from any vertex $$$u$$$, it is possible to go back to $$$u$$$ in finite time by walking on the graph under the described rules.

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$2\le m\le \min(2\cdot 10^5,n(n-1) )$$$, $$$1\le k\le 9$$$).

Each of the next $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ $$$(1\le u,v\le n,u\ne v,1\le w\le m)$$$, denoting an edge from $$$u$$$ to $$$v$$$ with weight $$$w$$$. It is guaranteed that there are no self-loops or multiple edges and each vertex has at least one edge starting from itself.

It is guaranteed that the out-degree of each vertex is at most $$$k$$$ and no two edges have equal weight.

Output

Print one integer: the number of tuples.

Examples

Input

4 6 3 4 2 1 1 2 2 2 4 3 4 1 4 4 3 5 3 1 6

Output

2

Input

5 5 1 1 4 1 5 1 2 2 5 3 4 3 4 3 2 5

Output

1

Input

6 13 4 3 5 1 2 5 2 6 3 3 1 4 4 2 6 5 5 3 6 4 1 7 4 3 8 5 2 9 4 2 10 2 1 11 6 1 12 4 6 13

Output

1

Note

For the first example, there are two tuples: $$$(1,1,3)$$$ and $$$(1,2,3)$$$. The blue edges in the picture denote the $$$c_i$$$-th smallest edges for each vertex, which Boboniu chooses to go through.

For the third example, there's only one tuple: $$$(1,2,2,2)$$$.

The out-degree of vertex $$$u$$$ means the number of edges outgoing from $$$u$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/23/2021 20:58:30 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|