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