Задача . 4. Орбитальные коридоры

Орбитальные коридоры

Станции пронумерованы от 1 до N. Каждый односторонний коридор ведёт из станции с меньшим номером в станцию с большим номером.

Маршрут — последовательность коридоров от станции 1 к станции N. Для каждой станции найдите число таких маршрутов, проходящих через неё. Станции 1 и N принадлежат каждому маршруту.

Входные данные

Первая строка: N M (2 <= N <= 200000, 1 <= M <= 400000). Далее M пар u v, где u < v. Повторяющихся рёбер нет; существует хотя бы один маршрут из 1 в N.

Выходные данные

Выведите в одной строке N чисел по модулю 1 000 000 007, разделяя соседние числа ровно одним пробелом. Для станции вне всех полных маршрутов выведите 0.

4 4
1 2
1 3
2 4
3 4

2 1 1 2

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

1 1 0 0 0 1