F. Сколько путей
1000 мс · 256 МБ · всё или ничего
В ориентированном ациклическом графе посчитайте количество различных путей из вершины в вершину . Ответ выведите по модулю .
Пути различаются набором рёбер: два ребра из в дают два разных пути.
Формат ввода
В первой строке - числа , , , (, ).
В следующих строках - рёбра , ациклического графа. Возможны кратные рёбра.
Формат вывода
Выведите количество путей из в по модулю .
Примеры
ввод
4 4 1 4 1 2 1 3 2 4 3 4
вывод
2
ввод
2 2 1 2 1 2 1 2
вывод
2
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.