Problem Description

In his later years, the gambling master atm became obsessed with stacking dice. This means placing one die on top of another. The stack must not be tilted, and must form a straight square pillar.

After long observation, atm discovered the secret of stable dice: some numbered faces repel each other when they touch!

First, we standardize the die: the face opposite $1$ is $4$, opposite $2$ is $5$, and opposite $3$ is $6$.

Suppose there are $m$ groups of repelling pairs. For each group, if the two faces with those numbers are in close contact, then the dice stack cannot be stable.

atm wants to compute how many different possible ways there are to stack the dice.

Two stacking methods are considered the same if and only if, at every height, the corresponding dice have the same orientation of the corresponding numbers.

Since the number of methods may be very large, output the result modulo $10^9+7$.

Do not underestimate how many dice atm has.

Input Format

The first line contains two integers $n$ and $m$.

$n$ is the number of dice.

The next $m$ lines each contain two integers $a$ and $b$, meaning that faces numbered $a$ and $b$ cannot be in close contact.

Output Format

Output one integer, the answer modulo $10^9+7$.

2 1
1 2

544

Hint

For $30\%$ of the testdata: $n \le 5$.

For $60\%$ of the testdata: $n \le 100$.

For $100\%$ of the testdata: $0 < n \le 10^9, m \le 36$.

Time limit: 2 seconds. Memory limit: 256 MB.

Lanqiao Cup 2015 Provincial Contest AB Group, Problem I.

Translated by ChatGPT 5