Ничто так не расслабляет Валю после подготовки тяжёлого контеста, как залипнуть в симулятор градостроения на весь вечер. Это происходит уже не в первый раз, поэтому у Вали есть большой город с многочисленными жителями и хорошей инфраструктурой. Сегодня Валя собирается добавить новое здание — первый в городе музей. Можно ожидать, что на открытие придёт много жителей. Поэтому нужно будет поставить ограждения, чтобы не создать давку. Ограждения понадобятся и внутри музея... На всё это уйдёт много время, поэтому Валя решил автоматизировать процесс, написав программу.

В игре доступны стойки с ограничительными лентами. Каждая такая стойка имеет 4 слота: из одного слота вытягивается лента, а 3 других слота свободны, и в них можно вставить ленту. Ленту можно натянуть между двумя стойками, вытянув её из одной стойки и вставив в свободный слот другой. Таким образом можно создавать сложные конструкции из лент.

Валина программа принимает на ввод план ограждений: он имеет вид графа из N вершин и M рёбер. В этом графе вершины соответствуют стойкам, а рёбра — исходящим из них лентам. Стойки пронумерованы от 1 до N. Только вот одному и тому же плану может соответствовать несколько конфигураций из лент. Помогите Вале реализовать функциональность, которая бы считала количество различных способов натянуть ленты так, чтобы получить данный граф.

Будем считать, что ленту можно натянуть только между двумя различными стойками, то есть петли в графе запрещены. Из каждой стойки можно вытянуть одну ленту, или не вытягивать ленту вовсе. В каждую стойку можно вставить не более трёх лент. Скажем также, что нельзя создавать кратные рёбра: то есть, нельзя провести ленту одновременно из стойки A в стойку B и из стойки B в стойку A.

Два способа считаются различными, если есть пара стоек (A, B) такая, что в одном из способов лента из стойки A вставлена в стойку B, а в другом — нет. При этом слот, куда вставлена лента, не имеет значения: способы, различающиеся только выбором слотов, считаются одинаковыми.

В первой строке через пробел даны два числа N и M — количество вершин и рёбер в плане ограждений (1 ≤ N ≤ 10⁵, 0 ≤ M ≤ 10⁵).

Далее идёт M строк, описывающие рёбра. В каждой строке через пробел даны два числа a_i, b_i — номера вершин, соединённых ребром (1 ≤ a_i, b_i ≤ N).

Гарантируется, что в графе нет петель и кратных рёбер.

Выведите единственное число — количество способов натянуть ленты между перегородками так, чтобы получить данный граф, по модулю 10⁹ + 7.