Life is a weighted directed graph consisting of $n$ neural nodes and $m$ nerves, where self-loops and multiple edges are allowed.

A nerve $i$ labeled $(u_i, v_i, w_i)$ connects two neural nodes $u_i \to v_i$ unidirectionally with a length of $w_i$.

The network of life is not overly complex; for any simple cycle, the sum of the lengths of all nerves contained within it is no greater than a constant $B$.

Neural nodes become excited at certain moments. Let $f(u, t)$ denote whether neural node $u$ is in an excited state at time $t$.

Excitation propagates along the nerves. For the $i$-th nerve $(u_i, v_i, w_i)$, if neural node $u_i$ is excited at time $t$, it will transmit a neural signal to node $v_i$, causing it to enter an excited state at time $t + w_i$.

The excited state of a neural node is not retained to the next moment. That is, after a neural node $u$ enters an excited state, it immediately transmits neural signals outward along other nerves; in subsequent moments, if no other nerve transmits a neural signal to it, the neural node will remain unexcited.

If, at the same moment, a node enters an excited state and recursively transmits a neural signal to itself, the excited state will still not be retained to the next moment. (In other words, if there exists a simple cycle with a total edge weight of 0 in the data, you can treat the entire simple cycle as a single neural node.)

At the beginning of life, a mysterious force stimulated neural node 1, causing it to enter an excited state at time 0. From this moment on, for countless moments, the signals of life have been propagating incessantly through the neural network.

After being baptized by Graham's number of moments, a powerful OIer—you—have finally arrived at neural node $n$ after overcoming numerous hardships. There, you see that life always tends toward cycles.

That is, it is guaranteed that after a sufficiently long time, neural node $n$ will repeatedly enter an excited state according to a certain pattern with a fixed time period.

You are now curious: what is the minimum period at which neural node $n$ enters an excited state at this time?

In other words, you need to find the smallest positive integer $p$ such that there exists a finite non-negative integer $M$ satisfying:

$$ \forall x \ge M, f(n, x) = f(n, x + p) $$

Since $p$ may be very large, you only need to output the result of $p$ modulo $10^9 + 9$.

Input

The first line contains three integers $n, m, type$, representing the number of neural nodes, the number of nerves, and the subtask ID, respectively. You can determine the value of $B$ through $type$. Specifically, for the example in the problem statement, $type = 0$.

The next $m$ lines each contain three integers $u_i, v_i, w_i$, describing that the $i$-th nerve points from neural node $u_i$ to neural node $v_i$ with length $w_i$.

Output

Output a single positive integer representing the result of $p$ modulo $10^9 + 9$.

Examples

Input 1

5 7 0
1 2 0
2 3 1
3 2 5
3 5 1
1 4 0
4 4 9
4 5 1

Output 1

18

Constraints

For all data, $2 \le n \le 5000$, $0 \le m \le 10^4$, $1 \le u_i, v_i \le n$, $0 \le w_i \le B \le 100$.

Subtasks

• Subtask 1 (1 pts): The directed graph formed by the nerves is a DAG, i.e., there are no simple cycles.
• Subtask 2 (8 pts): $n, B \le 10, m \le 15$.
• Subtask 3 (11 pts): The original graph is strongly connected. That is, any pair of neural nodes is mutually reachable via a directed path of nerves.
• Subtask 4 (10 pts): There exists at least one simple cycle containing node $n$.
• Subtask 5 (19 pts): The sets of nodes for all simple cycles are disjoint, and their total lengths are pairwise coprime.
• Subtask 6 (9 pts): The sets of nodes for all simple cycles are disjoint, and all total lengths are powers of prime numbers.
• Subtask 7 (18 pts): $B \le 30$.
• Subtask 8 (24 pts): No special restrictions.