Маленький Петя очень любит деревья. Недавно мама подарила ему дерево с 2n вершинами. Петя сразу же решил расположить это дерево на прямоугольной таблице, состоящей из 2 строк и n столбцов так, чтобы выполнялись следующие условия:
- Каждой клетке таблицы соответствует ровно одна вершина дерева и наоборот, каждой вершине дерева соответствует ровно одна клетка таблицы.
- Если две вершины дерева соединены ребром, то соответствующие им клетки имеют общую сторону.
Сейчас Пете интересно, сколько существует способов расположить его дерево на таблице. Он называет два расположения различными, если существует вершина дерева, которой соответствуют разные клетки таблицы в этих двух расположениях. Поскольку большие числа очень пугают Петю, выведите остаток от деления ответа на 1000000007 (109 + 7).
Выходные данные
Выведите единственное целое число — искомое количество способов расположить дерево на таблице, взятое по модулю 1000000007 (109 + 7).
Примечание
Пояснение к примеру 1 (ниже представлены все 12 вариантов расположения дерева на таблице):
1-3-2 2-3-1 5 4 6 6 4 5
| | | | | | | | | | | |
5 4 6 6 4 5 1-3-2 2-3-1
4-3-2 2-3-4 5-1 6 6 1-5
| | | | | | | |
5-1 6 6 1-5 4-3-2 2-3-4
1-3-4 4-3-1 5 2-6 6-2 5
| | | | | | | |
5 2-6 6-2 5 1-3-4 4-3-1
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3
2 3
4 3
5 1
6 2
|
12
|
|
2
|
4
1 2
2 3
3 4
4 5
5 6
6 7
7 8
|
28
|
|
3
|
2
1 2
3 2
4 2
|
0
|