Сколько кратчайших путей

Сколько существует различных кратчайших путей от вершины 1 до вершины $n$?

Ответ может быть огромным, поэтому выведите остаток от его деления на $10^9 + 7$. Если пути нет, выведите 0.

В первой строке числа $n$ от $1$ до $2 \cdot 10^5$ и $m$ от $0$ до $2 \cdot 10^5$. Во второй строке $2m$ чисел: пары концов рёбер.

Одно число.

Ведите рядом с расстоянием ещё и количество путей. Когда сосед впервые получает расстояние, он наследует количество у текущей вершины; когда встречается снова и расстояние совпало, количества складываются. Обход в ширину гарантирует, что к моменту обработки вершины её количество уже посчитано целиком.