EduBrick

F. Сколько путей

1000 мс · 256 МБ · всё или ничего

В ориентированном ациклическом графе посчитайте количество различных путей из вершины ss в вершину tt. Ответ выведите по модулю 109+710^9+7.

Пути различаются набором рёбер: два ребра из uu в vv дают два разных пути.

Формат ввода

В первой строке - числа nn, mm, ss, tt (1≤n≤1051 \le n \le 10^5, 0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

В следующих mm строках - рёбра uu, vv ациклического графа. Возможны кратные рёбра.

Формат вывода

Выведите количество путей из ss в tt по модулю 109+710^9+7.

Примеры

ввод
4 4 1 4
1 2
1 3
2 4
3 4
вывод
2
ввод
2 2 1 2
1 2
1 2
вывод
2
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.