E. Дерево и таблица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Петя очень любит деревья. Недавно мама подарила ему дерево с 2n вершинами. Петя сразу же решил расположить это дерево на прямоугольной таблице, состоящей из 2 строк и n столбцов так, чтобы выполнялись следующие условия:

  1. Каждой клетке таблицы соответствует ровно одна вершина дерева и наоборот, каждой вершине дерева соответствует ровно одна клетка таблицы.
  2. Если две вершины дерева соединены ребром, то соответствующие им клетки имеют общую сторону.

Сейчас Пете интересно, сколько существует способов расположить его дерево на таблице. Он называет два расположения различными, если существует вершина дерева, которой соответствуют разные клетки таблицы в этих двух расположениях. Поскольку большие числа очень пугают Петю, выведите остаток от деления ответа на 1000000007 (109 + 7).

Входные данные

Первая строка содержит единственное целое число n (1 ≤ n ≤ 105). Следующие (2n - 1) строк содержат по два целых числа ai и bi (1 ≤ ai, bi ≤ 2n; ai ≠ bi), которые обозначают номера вершин, соединенных соответствующим ребром.

Считайте, что вершины дерева пронумерованы целыми числами от 1 до 2n. Гарантируется, что заданный во входных данных граф является деревом, то есть связным ациклическим неориентированным графом.

Выходные данные

Выведите единственное целое число — искомое количество способов расположить дерево на таблице, взятое по модулю 1000000007 (109 + 7).

Примеры
Входные данные
3
1 3
2 3
4 3
5 1
6 2
Выходные данные
12
Входные данные
4
1 2
2 3
3 4
4 5
5 6
6 7
7 8
Выходные данные
28
Входные данные
2
1 2
3 2
4 2
Выходные данные
0
Примечание

Пояснение к примеру 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