赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。
假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
atm想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多，请输出模 109+7 的结果。
输入格式 第一行包含两个整数 n,m，分别表示骰子的数目和排斥的组数。
接下来 m 行，每行两个整数 a,b，表示 a 和 b 数字不能紧贴在一起。
输出格式 共一个数，表示答案模 109+7 的结果。
数据范围 1≤n≤109, 1≤m≤36, 1≤a,b≤6 输入样例： 2 1 1 2 输出样例： 544
import java.util.*;
public class Main
{
static int n,m,N=6,mod=1000000007;
static int a[][]=new int [N][N],f[][]=new int[N][N];
static int map(int x){
return (x+3)%6;
}
static void mul(int c[][],int a[][],int b[][]){
int t[][]=new int [N][N];
for(int i=0;i for(int j=0;j for(int k=0;k t[i][j]=(int)((t[i][j]+(long)a[i][k]*b[k][j])%mod); } } } for(int i=0;i for(int j=0;j c[i][j]=t[i][j]; } } } public static void main(String args[]) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); for(int i=0;i for(int i=0;i while((m--)>0){ int x,y; x=sc.nextInt(); y=sc.nextInt(); x--;y--; a[map(y)][x]=0; a[map(x)][y]=0; } n--; while(n>0){ if(n%2==1)mul(f,f,a); mul(a,a,a); n>>=1; } int ans=0; for(int i=0;i ans=(ans+f[0][i])%mod; } System.out.println(ans); } }