Windy's Timed Journey

Given a directed graph with \(n\) nodes numbered from 1 to \(n\), Windy starts his journey from node 1 and must reach node \(n\) exactly at time \(t\). The graph is represented by \(m\) directed edges and each edge has a fixed travel time. Note that Windy is not allowed to wait at any node; he must continuously traverse the edges, and the time taken to traverse an edge is exactly as specified.

Your task is to determine the number of distinct paths from node 1 to node \(n\) that take exactly \(t\) units of time. Since the answer may be very large, output it modulo \(2009\).

The problem can be modeled using dynamic programming. Define \(dp(\tau, v)\) as the number of ways to reach node \(v\) at time \(\tau\). With an edge \((u, v)\) having travel time \(w\), the transition is given by:

[ \displaystyle dp(\tau + w, v) ;+=; dp(\tau, u), \quad \text{for each edge } (u, v) \text{ with travel time } w, ]

with the initial condition \(dp(0, 1) = 1\) and the answer being \(dp(t, n)\).

inputFormat

The input consists of multiple lines:

• The first line contains three integers \(n\), \(m\), and \(t\):
  • \(n\): the number of nodes.
  • \(m\): the number of directed edges.
  • \(t\): the required total travel time.
• The following \(m\) lines each contain three integers \(u\), \(v\), and \(w\), representing a directed edge from node \(u\) to node \(v\) that takes \(w\) time units to traverse.

outputFormat

Output a single integer: the number of distinct paths from node 1 to node \(n\) that take exactly \(t\) time units, modulo \(2009\).

sample

3 3 3
1 2 1
2 3 2
1 3 3

2