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