Говорят, что высоко в горах (но, конечно, не в нашем районе) всё ещё сохранился красивый древний обычай - похищать невесту. Некий джигит как раз собрался это сделать. В распоряжении джигита есть прекрасный конь, его верный соратник в делах сердечных. Для того, чтобы достойно совершить похищение, джигиту придётся хорошенько тренироваться в условиях, приближенных к реальным.
Для тренировок у джигитов есть специальное место. На нём выделены N пунктов, пронумерованные от 1 до N, и M дорожек. Согласно древнему обычаю, каждая из дорожек имеет единственное направление, в котором должен двигаться наездник. Двигаться по соответствующей дорожке в противоположном направлении опасно для жизни (все остальные джигиты воспринимают это как кровную обиду – со всеми вытекающими отсюда последствиями). Также каждая из дорожек имеет сложность, выраженную натуральным числом. Возможно существование нескольких дорожек между парой пунктов, или существование круговой дорожки, т.е. дорожки, для который начальный и конечный пункты совпадают.
Маршрутом назовём такую непустую последовательность дорожек, в которой каждая следующая дорожка (кроме первой) начинается в том пункте, где закончилась предыдующая. Полезным назовем маршрут, в котором сложность каждой дорожки (кроме начальной) строго выше предыдущей.
Джигит должен избрать маршрут, который начинается и заканчивается в пункте 1. Естественно, в интересах дела, джигит должен пользоваться только полезными маршрутами.
Ваша задача – найти, сколько различных полезных маршрутов имеется в распоряжении джигита. Так как таких маршрутов может быть очень много, вынесите остаток при делении их количества на 1000000000.
Первая строка содержит числа N и M. Каждая из следующих M строк содержит целые числа A_i, B_i, C_i – начальный и конечный пункты i-ой дорожки и её сложность, соответственно.
1 ≤ N ≤ 50000, 1 ≤ M ≤ 100000, 1 ≤ C_i ≤ 30000.
Единственное целое число – остаток от деления количества полезных маршрутов на 1000000000.