В Сильвертауне есть
N районов с номерами от
1 до
N и
M дорог с номерами от
1 до
M. Используя дорогу
i, вы можете добраться из района
Ai в район
Bi или наоборот за один час.
Сколько существует путей, по которым можно добраться из района
1 в район
N как можно быстрее?
Поскольку число может быть огромным, выведите его по модулю
109+7
Формат входных данных
Первая строка содержит два целых числа
N и
M. Далее идет
M строк, в каждой из которых записано по 2 числа:
Ai и
Bi.
Ограничения
2 ≤ N ≤ 2×1050 ≤ M ≤ 2×1051 ≤ Ai < Bi ≤ NПары (Ai,Bi) уникальны.Все значения во входных данных целые числа.
Формат выходных данных
Выведите ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
2 4
1 2
2 3
1 3
3 4
|
2
|
|
2
|
4 3
1 3
2 3
2 4
|
1
|
|
3
|
2 0
|
0
|
|
4
|
7 8
1 3
1 4
2 3
2 4
2 5
2 6
5 7
6 7
|
4
|