Кажуть, що високо у горах (але, звичайно ж, не у нашому районі) все ще зберігся красивий стародавній звичай - викрадати наречену. Деякий джигіт як раз зібрався це зробити. У розпорядженні джигіта є прекрасний кінь, його вірний соратник у справах сердечних. Для того, щоб гідно здійснити викрадення, джигіту доведеться добре тренуватись в умовах, наближених до реальних. Для тренувань у джигітів є спеціальне місце. На ньому виділено \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}. \OutputFile Єдине ціле число -- остачу при діленні кількості корисних маршрутів на \textbf{1000000000}.