Маленький Петя очень любит деревья. Недавно мама подарила ему дерево с 2n вершинами. Петя сразу же решил расположить это дерево на прямоугольной таблице, состоящей из 2 строк и n столбцов так, чтобы выполнялись следующие условия:
Сейчас Пете интересно, сколько существует способов расположить его дерево на таблице. Он называет два расположения различными, если существует вершина дерева, которой соответствуют разные клетки таблицы в этих двух расположениях. Поскольку большие числа очень пугают Петю, выведите остаток от деления ответа на 1000000007 (109 + 7).
Первая строка содержит единственное целое число n (1 ≤ n ≤ 105). Следующие (2n - 1) строк содержат по два целых числа ai и bi (1 ≤ ai, bi ≤ 2n; ai ≠ bi), которые обозначают номера вершин, соединенных соответствующим ребром.
Считайте, что вершины дерева пронумерованы целыми числами от 1 до 2n. Гарантируется, что заданный во входных данных граф является деревом, то есть связным ациклическим неориентированным графом.
Выведите единственное целое число — искомое количество способов расположить дерево на таблице, взятое по модулю 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-14-3-2 2-3-4 5-1 6 6 1-5 | | | | | | | |5-1 6 6 1-5 4-3-2 2-3-41-3-4 4-3-1 5 2-6 6-2 5| | | | | | | |5 2-6 6-2 5 1-3-4 4-3-1
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач