Задан неориентированный связный граф, состоящий из \(n\) вершин и \(m\) ребер. Граф не содержит петель (рёбер из вершины в себя же) и кратных ребер (то есть между каждой парой вершин не более одного ребра). Вершины графа пронумерованы от \(1\) до \(n\).
Найдите количество путей из вершины \(s\) в \(t\), длина которых отличается от длины кратчайшего пути из \(s\) в \(t\) не более, чем на \(1\). Необходимо учесть все подходящие пути, даже если они проходят по одной и той же вершине или ребру более одного раза (то есть, не являются простыми).
Граф, состоящий из \(6\) вершин и \(8\) ребер. Например, пусть \(n = 6\), \(m = 8\), \(s = 6\) и \(t = 1\), а граф выглядит как на рисунке выше. Тогда длина кратчайшего пути из \(s\) в \(t\) равна \(1\). Рассмотрим все пути, длина которых не более \(1 + 1 = 2\).
- \(6 \rightarrow 1\). Длина пути равна \(1\).
- \(6 \rightarrow 4 \rightarrow 1\). Длина пути равна \(2\).
- \(6 \rightarrow 2 \rightarrow 1\). Длина пути равна \(2\).
- \(6 \rightarrow 5 \rightarrow 1\). Длина пути равна \(2\).
Всего существует \(4\) подходящих пути.
Выходные данные
Для каждого тестового случая выведите единственное число — количество путей из \(s\) в \(t\) таких, что их длина отличается от длины кратчайшего пути не более, чем на \(1\).
Так как это число может быть слишком большим, выведите его по модулю \(10^9 + 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 4
1 4
1 2
3 4
2 3
2 4
6 8
6 1
1 4
1 6
1 5
1 2
5 6
4 6
6 3
2 6
5 6
1 3
3 5
5 4
3 1
4 2
2 1
1 4
8 18
5 1
2 1
3 1
4 2
5 2
6 5
7 3
8 4
6 4
8 7
1 4
4 7
1 6
6 7
3 8
8 5
4 5
4 3
8 2
|
2
4
1
11
|