Вам дан ациклический ориентированный граф. Найдите в нем количество путей от вершины A до вершины B. Так как потенциально различных путей может быть очень много, то выведите остаток этого числа по модулю 109 + 7.
В первой строке дано количество вершин в графе n и ребер m (1 ≤ n ≤ 105, 0 ≤ m ≤ 5 ⋅ 105). В каждой из следующих m строк описаны ребра. Каждое ребро задается своим началом и концом. В последней строке даны вершины A и B (1 ≤ A, B ≤ n).
Выведите единственное число – количество путей от A до B по модулю 109 + 7.
|
3 3 1 2 1 2 2 3 1 3 |
2 |
|
5 3 1 2 3 4 4 5 1 5 |
0 |
|
3 3 1 2 2 3 1 3 1 1 |
1 |