Дракон і дороги
Обмеження: 2 сек., 256 МіБ
Дракон Віталій потрапив до нового міста і знайшов його карту. На карті позначено \(n\) контрольних точок та \(m\) доріг, які їх з’єднують. Відомо, що довжина кожної дороги дорівнює 47.
Віталію необхідно добратися з точки \(a\) до точки \(b\), подолавши при цьому якомога меншу відстань. Ваше завдання — сказати, скількома способами Дракон зможе це зробити. Оскільки відповідь може бути дуже великою, виведіть кількість різних шляхів за модулем простого числа \(10^9 + 7\).
Вхідні дані
У першому рядку задано два натуральних числа \(n\) та \(m\) — кількість точок і кількість доріг відповідно.
У другому рядку задано два натуральних числа \(a\) та \(b\) — номери точок, між якими Віталій хоче подорожувати.
У наступних \(m\) рядках задано по два числа \(u_i\) та \(v_i\), які означають, що між точками з номерами \(u_i\) та \(v_i\) є дорога.
Вихідні дані
У єдиному рядку виведіть одне ціле число — кількість різних шляхів мінімальної довжини між точками \(a\) та \(b\) за модулем просто числа \(10^9 +7\)
Обмеження
\(1 \le n, m \le 10^5\),
\(1 \le a, b, u_i, v_i \le n\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 1 4 1 2 1 3 2 4 3 4 | 2 |
Примітки
Можливі шляхи: 1-2-4, 1-3-4
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|