Основная предпосылка справедливости не должна быть правильной, но должна быть сильной. Вот почему справедливость всегда побеждает.
Пчела Циндерсворм. Коёми с ним знаком.
Пчёлы, как известно, живут на дереве. Точнее в полном двоичном дереве с n вершинами, пронумерованными от 1 до n. Вершина с номером 1 является корнем, а предок i-й (2 ≤ i ≤ n) вершины имеет номер 
. Учтите, что все рёбра в дереве неориентированные.
Коёми добавил m дополнительных неориентированных рёбер, делая дом пчёл сложнее. А вам нужно посчитать количество простых путей в полученном графе, по модулю 109 + 7. Простой путь это последовательность из вершин, в которой каждые две соседние вершины соединены ребром, а также рёбер, их соединяющих. Кроме того, простой путь не содержит никакую вершину более одного раза. Учтите, что путь из одной вершины также является простым путём. Обратитесь к примерам для лучшего понимания условия.
Выходные данные
Выведите единственное число — количество простых путей в итоговом графе по модулю 109 + 7.
Примечание
В первом тестовом примере простыми путями являются: (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 путей в сумме.)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 0
|
9
|
|
2
|
3 1
2 3
|
15
|
|
3
|
2 4
1 2
2 1
1 2
2 1
|
12
|