Stacking Dice

In this problem, a veteran gambler named atm has become fascinated with stacking dice. The dice are stacked exactly one on top of the other to form a perfect cuboid (i.e. a straight column) without any tilt. However, through long‐term observation, atm discovered a secret: certain faces on adjacent dice repel each other when they touch!

The dice are standard with fixed opposing faces: \(1\) is opposite to \(4\), \(2\) is opposite to \(5\), and \(3\) is opposite to \(6\). Suppose there are \(m\) pairs of numbers that repel each other. In each forbidden pair, if the two numbers appear on the two touching faces (one on the lower dice’s top and the other on the upper dice’s bottom), the stack becomes unstable.

Two stacking configurations are considered identical if and only if, at every level, the faces in the corresponding positions (with their orientations) are the same.

Given the number of dice \(n\) (i.e. the height of the stack) and \(m\) repelling (forbidden) pairs, calculate the number of distinct stable stacking configurations. Since the number may be huge, output the answer modulo \(10^9+7\).

Notes on Dice Orientation:

• A single die can be oriented in 24 different ways.
• If the top face is fixed, the bottom face is automatically determined (it must be the face opposite to the top face), and the remaining 4 side faces can be rotated in 4 ways.
• When stacking two dice, the interface is the lower die's top face and the upper die's bottom face. For the upper die, if you want a specified number on the bottom face then there are exactly 4 valid orientations.

The forbidden condition applies as follows: Suppose the lower die's top face shows number \(X\) and the upper die's bottom face shows \(Y\). If \(\{X, Y\}\) matches any of the forbidden pairs (order does not matter), the configuration is invalid.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers \(n\) and \(m\). Here, \(n\) (\(1 \le n \le 10^{9}\)) is the number of dice (the height of the stack) and \(m\) is the number of forbidden pairs.
2. The next \(m\) lines each contain two distinct integers \(a\) and \(b\) (each from 1 to 6) indicating that if these two numbers appear on the contacting faces of two dice, the stack becomes unstable.

outputFormat

Output a single integer, which is the number of distinct stable stacking configurations modulo \(10^9+7\).

sample

1 0

24