Bride kidnapping
High in the mountains, though not in our region, an ancient and beautiful custom still exists: bride kidnapping. A certain dzhigit is preparing to partake in this tradition. He has a magnificent horse, his loyal companion in matters of the heart. To execute the kidnapping with honor, the dzhigit must train under conditions that closely mimic the real event.
For this training, dzhigits have a designated area. This area consists of N points, numbered from 1 to N, and M paths. According to tradition, each path is one-way, and traveling in the opposite direction is perilous, as it is considered a grave insult by other dzhigits, with dire consequences. Each path also has a difficulty level, represented by a natural number. There may be multiple paths between two points or even a circular path, where the start and end points are the same.
A route is defined as a non-empty sequence of paths where each subsequent path (except the first) begins at the point where the previous one ended. A useful route is one where the difficulty of each path (except the first) is strictly greater than the previous one.
The dzhigit must select a route that begins and ends at point 1. Naturally, he should only consider useful routes.
Your task is to determine how many different useful routes are available to the dzhigit. Since there may be a large number of such routes, compute the remainder when their count is divided by 1000000000.
Input
The first line contains the numbers N and M. Each of the next M lines contains integers A_i, B_i, C_i - the starting and ending points of the i-th path and its difficulty, respectively.
1 ≤ N ≤ 50000, 1 ≤ M ≤ 100000, 1 ≤ C_i ≤ 30000.
Output
Output a single integer - the remainder when the number of useful routes is divided by 1000000000.