Codeforces Round 184 (Div. 2) |
---|
Закончено |
У Оли есть ориентированный невзвешенный граф, состоящий из n вершин и m ребер. Будем считать, что вершины графа пронумерованы от 1 до n некоторым способом. Тогда для каждого ребра графа, идущего от вершины v к вершине u, выполняется неравенство: v < u.
Теперь Оле интересно, сколько существует способов добавить в граф произвольное (возможно нулевое) количество ребер так, чтобы для полученного графа были выполнены условия:
Два способа будем считать различными, если будет существовать пара вершин i, j (i < j) такая, что в первом полученном графе будет существовать ребро из i в j, а во втором — нет.
Помогите Оле. Так как искомое количество способов может быть достаточно большим, выведите его остаток от деления на 1000000007 (109 + 7).
В первой строке записаны три целых числа через пробел n, m, k (2 ≤ n ≤ 106, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106).
Во последующих m строках записано описание ребер изначального графа. В i-ой строке записана пара целых чисел через пробел ui, vi (1 ≤ ui < vi ≤ n) — номера вершин, между которыми есть ориентированное ребро из ui в vi.
Гарантируется, что между любой парой вершин ui, vi существует не более одного ребра. Также гарантируется, что ребра графа записаны в порядке неубывания величин ui. Если из вершины ui имеется несколько ребер, то гарантируется, что эти ребра заданы в порядке возрастания величин vi.
Выведите единственное целое число — ответ на задачу по модулю 1000000007 (109 + 7).
7 8 2
1 2
2 3
3 4
3 6
4 5
4 7
5 6
6 7
2
7 0 2
12
7 2 1
1 3
3 5
0
В первом примере есть два способа: первый — это ничего не добавлять, второй — добавить единственное ребро из вершины 2 в вершину 5.
Название |
---|