F. Коала и блокнот
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Страна коал состоит из $$$n$$$ городов и $$$m$$$ двусторонних дорог, их соединяющих. Дороги пронумерованы от $$$1$$$ до $$$m$$$ в порядке входных данных. Гарантируется, что можно добраться от каждого города до любого другого города.

Коала начинает путешествие из города $$$1$$$. Каждый раз, когда он проходит по дороге, он записывает её номер в блокнот. Он не делает пробелов между числами, так что все записи склеятся в одно большое число.

Перед тем как отправится в свой путь, Коала интересуется какое число может получится в блокноте в зависимости от конечного пункта. Для каждого возможного конечного пункта выясните, какое наименьшее число может для него получиться?

Так как эти числа могут быть достаточно большими, вычислите их по модулю $$$10^9+7$$$. Обратите внимание, что нужно вычислить остаток минимального возможного числа, не минимально возможный остаток.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 10^5, n - 1 \le m \le 10^5$$$) — количество городов и количество дорог соответственно.

$$$i$$$-я из следующих $$$m$$$ строк содержит целые числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$), обозначающие двустороннюю дорогу между $$$x_i$$$ и $$$y_i$$$.

Гарантируется, что для каждой пары городов есть не более одной дороги их соединяющей, и что можно добраться из каждого города до любого другого.

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

Выведите $$$n - 1$$$ целое число — ответ для каждого города за исключением первого.

$$$i$$$-е число должно быть равно наименьшему числу, которое получилось бы для конечной точки $$$i+1$$$. Так как это число может быть достаточно большим, выведите его остаток по модулю $$$10^9+7$$$.

Примеры
Входные данные
11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
Выходные данные
1
12
123
1234
12345
123456
1234567
12345678
123456789
345678826
Входные данные
12 19
1 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 11
11 12
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
Выходные данные
1
12
13
14
15
16
17
18
19
1210
121011
Входные данные
12 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 3
1 4
1 10
Выходные данные
1
12
13
134
1345
13456
1498
149
14
1410
141011