G. Подсчёт коротких путей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан неориентированный связный граф, состоящий из $$$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$$$ подходящих пути.

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

В первой строке входных данных задано число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Перед каждым набором входных данных записана пустая строка.

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

Вторая строка содержит два числа $$$s$$$ и $$$t$$$ ($$$1 \le s, t \le n$$$, $$$s \neq t$$$) — номера начальной и конечной вершины пути.

В следующих $$$m$$$ строках содержатся описания ребер: в $$$i$$$-й строке заданы два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$) — номера вершин, которые соединяют $$$i$$$-е ребро. Гарантируется, что граф является связным и не содержит петель и кратных рёбер.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных теста не превосходит $$$2 \cdot 10^5$$$. Аналогично, гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных теста не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого тестового случая выведите единственное число — количество путей из $$$s$$$ в $$$t$$$ таких, что их длина отличается от длины кратчайшего пути не более, чем на $$$1$$$.

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

Пример
Входные данные
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