Mountain Trails

A mountain hiker is planning training routes in the mountains. For training, there is a special area with $N$ waypoints, numbered from $1$ to $N$, and $M$ trails. Each trail can only be traveled in one direction (uphill or downhill). Each trail also has a natural number as its difficulty rating. There may be multiple trails between two waypoints, or even a loop trail (where the start and end points coincide).

A route is a nonempty sequence of trails such that each subsequent trail (except the first) begins where the previous one ended. A useful training route is one where the difficulty of each trail (except the first) is strictly greater than that of the previous one.

The hiker must select a route that starts and ends at the base camp (waypoint $1$). They may only consider useful training routes.

Your task is to count the number of different useful training routes available to the hiker. Since there may be very many, output the remainder when their number is divided by $1000000000$.