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