N. Сколько кратчайших

Неориентированный граф задан списком рёбер. Посчитайте количество кратчайших путей из вершины 1 в вершину $n$.

Путей может быть очень много, поэтому ответ выводится по модулю $10^9 + 7$.

Считается это тем же обходом: у вершины на расстоянии $d$ число кратчайших путей равно сумме этих чисел по соседям на расстоянии $d - 1$. Обход в ширину обрабатывает вершины по возрастанию расстояния, поэтому к моменту обработки все нужные значения уже готовы.

Первая строка содержит числа $n$ ($1 \le n \le 10^5$) и $m$ ($0 \le m \le 2 \cdot 10^5$).

Далее идут $m$ строк с рёбрами простого графа.

Одно число — количество кратчайших путей по модулю $10^9 + 7$, или 0, если пути нет.