Codeforces Round 153 (Div. 1) |
---|
Закончено |
Маленький Петя очень любит деревья. Недавно мама подарила ему дерево с 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).
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
Название |
---|