| Codeforces Round 439 (Div. 2) |
|---|
| Закончено |
Основная предпосылка справедливости не должна быть правильной, но должна быть сильной. Вот почему справедливость всегда побеждает.
Пчела Циндерсворм. Коёми с ним знаком.
Пчёлы, как известно, живут на дереве. Точнее в полном двоичном дереве с n вершинами, пронумерованными от 1 до n. Вершина с номером 1 является корнем, а предок i-й (2 ≤ i ≤ n) вершины имеет номер 
. Учтите, что все рёбра в дереве неориентированные.
Коёми добавил m дополнительных неориентированных рёбер, делая дом пчёл сложнее. А вам нужно посчитать количество простых путей в полученном графе, по модулю 109 + 7. Простой путь это последовательность из вершин, в которой каждые две соседние вершины соединены ребром, а также рёбер, их соединяющих. Кроме того, простой путь не содержит никакую вершину более одного раза. Учтите, что путь из одной вершины также является простым путём. Обратитесь к примерам для лучшего понимания условия.
В первой строке содержатся два целых числа n и m (1 ≤ n ≤ 109, 0 ≤ m ≤ 4) — число вершин в дереве и число добавленных рёбер, соответственно.
В следующих m строках содержатся пары целых чисел u и v (1 ≤ u, v ≤ n, u ≠ v), которые описывают ребро, добавленное между вершинами u и v.
Учтите, что в итоговом графе могут быть кратные рёбра.
Выведите единственное число — количество простых путей в итоговом графе по модулю 109 + 7.
3 0
9
3 1
2 3
15
2 4
1 2
2 1
1 2
2 1
12
В первом тестовом примере простыми путями являются: (1); (2); (3); (1, 2); (2, 1); (1, 3); (3, 1); (2, 1, 3); (3, 1, 2). (Для простоты тут не указаны рёбра в пути, так как в графе нет кратных рёбер)
Во втором тестовом примере простыми путями являются: (1); (1, 2); (1, 2, 3); (1, 3); (1, 3, 2) и аналогичные пути с началами в 2 и 3. (5 × 3 = 15 в итоге.)
В третьем тестовом примере простыми путями являются: (1); (2); и любой путь из одного ребра, пройденного в каком-то направлении. (2 + 5 × 2 = 12 путей в сумме.)
