D. Постоянная вездесущесть
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Основная предпосылка справедливости не должна быть правильной, но должна быть сильной. Вот почему справедливость всегда побеждает.

Пчела Циндерсворм. Коёми с ним знаком.

Пчёлы, как известно, живут на дереве. Точнее в полном двоичном дереве с 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 путей в сумме.)