Nothing relaxes Valya after preparing for a tough contest more than getting lost in a city-building simulator for the whole evening. This game session is not the first, and Valya already has a large city with numerous residents and good infrastructure. Today, Valya plans to add a new building — the first museum in the city. Many residents are expected to come to the opening. Therefore, barriers will need to be set up to avoid overcrowding. Barriers will also be needed inside the museum... All of this will take a lot of time, so Valya decided to automate the process by writing a program.

There are stands with restraining tapes available in the game. Each stand has 4 slots: one slot is used to pull out the tape, and the other 3 slots are free and can be used to insert tapes. Tapes can be stretched between two stands by pulling it out from one stand and inserting it into a free slot of another stand. This way, complex structures can be created from tapes.

Valya’s program takes as input a plan of barriers, which is represented as a graph with N vertices and M edges. In this graph, vertices correspond to stands, and edges correspond to tapes extending from the stands. The stands are numbered from 1 to N. However, the same plan can correspond to multiple tape configurations. Help Valya implement a functionality that calculate the number of different ways to stretch the tapes to obtain the given graph.

It is assumed that a tape can only be stretched between two different stands, i.e., loops in the graph are not allowed. From each stand, one tape can be pulled out or no tape can be pulled out at all. Each stand can have a maximum of three tapes inserted into it. It is also not allowed to create multiple edges, i.e., it is not possible to have a tape going from stand A to stand B and another tape going from stand B to stand A simultaneously.

Two ways are considered different if there is a pair of stands (A, B) and in one way the tape from stand A is inserted into stand B, while in the other way, it is not. The slot where the tape is inserted does not matter: ways that only differ in the choice of slots are considered the same.

The first line contains two integers N and M separated by a space, representing the number of vertices and edges in the barrier plan (1 ≤ N ≤ 10⁵, 0 ≤ M ≤ 10⁵).

Next are M lines describing the edges. Each line contains two integers a_i, b_i separated by a space, representing the numbers of vertices connected by an edge (1 ≤ a_i, b_i ≤ N).

It is guaranteed that the graph does not contain loops or multiple edges.

Output a single number — the number of ways to stretch the tapes between the barriers to obtain the given graph, modulo 10⁹ + 7.