У грі є \(n\) рівнів, з’єднаних \(m\) телепортами, і ваше завдання — потрапити з рівня 1 на рівень \(n\).

Гру розроблено таким чином, що в базовому графі немає циклів.

Скількома способами ви можете завершити гру?

Обмеження

• \(1≤n≤10^5\)
• \(1≤m≤2 ⋅10^5\)
• \(1≤a,b≤n\)

Формат вхідних даних

У першому рядку є два цілих числа \(n\) і \(m\): кількість рівнів і телепортів. Рівні пронумеровані \(1,2,…,n\).

Після цього є \(m\) рядків, що описують телепорти. У кожному рядку є два цілих числа \(a\) і \(b\): є телепортатор з рівня \(a\) на рівень \(b\).

Формат вихідних даних

Виведіть одне ціле число: кількість способів, якими ви можете завершити гру. Оскільки результат може бути великим, виведіть його за модулем \(10^9+7\).

Приклад вхідних даних

4 5
1 2
2 4
1 3
3 4
1 4

Приклад вихідних даних

3