D. Оля и граф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Оли есть ориентированный невзвешенный граф, состоящий из n вершин и m ребер. Будем считать, что вершины графа пронумерованы от 1 до n некоторым способом. Тогда для каждого ребра графа, идущего от вершины v к вершине u, выполняется неравенство: v < u.

Теперь Оле интересно, сколько существует способов добавить в граф произвольное (возможно нулевое) количество ребер так, чтобы для полученного графа были выполнены условия:

  1. Из любой вершины с номером i (i < n) достижимы вершины с номерами i + 1, i + 2, ..., n.
  2. Для каждого ребра графа, идущего от вершины v к вершине u, выполняется неравенство: v < u.
  3. Между любыми двумя вершинами существует не более одного ребра.
  4. Кратчайшее расстояние между парой вершин i, j (i < j), для которых верно, что j - i ≤ k, равно j - i ребер.
  5. Кратчайшее расстояние между парой вершин i, j (i < j), для которых верно, что j - i > k, равно либо j - i, либо j - i - k ребер.

Два способа будем считать различными, если будет существовать пара вершин 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.