1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
| #include<cstdio> #include<cassert> #include<cstring> #include<algorithm> using namespace std;
const int MOD=1e9+7,VARA=500000003,VARB=541031193,N=105,M=N*N; #define cint const int &
inline int Rint(int &r){ int b=1,c=getchar();r=0; while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar(); while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar(); return r*=b; } inline int Mul(cint a,cint b){return 1ll*a*b%MOD;} inline int Pow(cint a,cint b){return b? Mul(Pow(Mul(a,a),b>>1),(b&1)? a:1):1;} inline int Add(cint a,cint b){return a+b>=MOD? a+b-MOD:a+b;} inline int Sub(cint a,cint b){return a-b<0? a-b+MOD:a-b;} #define square(a) Mul(a,a) const int INV3=Pow(3,MOD-2);
struct NCOMPLEX{ #define cnc const NCOMPLEX & #define oper(typ) inline friend typ operator int a,b; NCOMPLEX(){} NCOMPLEX(cint A,cint B):a(A),b(B){} oper(NCOMPLEX) *(cnc A,cnc B){return NCOMPLEX(Sub(Mul(A.a,B.a),Mul(A.b,B.b)),Add(Mul(A.a,B.b),Mul(B.a,A.b)));} oper(NCOMPLEX) *(cnc A,cint B){return NCOMPLEX(Mul(A.a,B),Mul(A.b,B));} oper(NCOMPLEX) +(cnc A,cnc B){return NCOMPLEX(Add(A.a,B.a),Add(A.b,B.b));} oper(NCOMPLEX) -(cnc A,cnc B){return NCOMPLEX(Sub(A.a,B.a),Sub(A.b,B.b));} oper(NCOMPLEX) -(cnc A){return NCOMPLEX(Sub(0,A.a),Sub(0,A.b));} inline void operator +=(cnc A){(*this)=(*this)+A;} inline void operator -=(cnc A){(*this)=(*this)-A;} inline void operator *=(cnc A){(*this)=(*this)*A;} inline friend NCOMPLEX inv(cnc A){ return NCOMPLEX(A.a,Sub(0,A.b)) *Pow(Add(square(A.a),square(A.b)),MOD-2); } #undef cnc #undef oper };
const NCOMPLEX con[3]={NCOMPLEX(1,0),NCOMPLEX(VARA,VARB),NCOMPLEX(VARA,VARB)*NCOMPLEX(VARA,VARB)};
int n,m; int edg[M][3]; NCOMPLEX mat[N][N];
NCOMPLEX Det(){ NCOMPLEX ans(1,0); for(int i=1;i<n;i++){ for(int j=i;j<n;j++) if(mat[j][i].a || mat[j][i].b){ if(i==j) break; swap(mat[i],mat[j]),ans=-ans; break; } ans=ans*mat[i][i]; NCOMPLEX tmp=inv(mat[i][i]); for(int j=i+1;j<n;j++){ NCOMPLEX now=mat[j][i]*tmp; for(int k=i;k<n;k++) mat[j][k]-=now*mat[i][k]; } } return ans; } inline void IDFT(NCOMPLEX *p){ int i; NCOMPLEX tmp[3]; tmp[0]=p[0],tmp[1]=p[1],tmp[2]=p[2]; p[0]=tmp[0]+tmp[1]+tmp[2]; p[1]=tmp[0]+tmp[1]*inv(con[1])+tmp[2]*inv(con[2]); p[2]=tmp[0]+tmp[1]*inv(con[2])+tmp[2]*inv(con[1]); for(i=0;i<3;++i) p[i]=p[i]*INV3; } int Calc(){ NCOMPLEX res[3]; for(int i=0;i<3;i++){ memset(mat,0,sizeof mat); NCOMPLEX w[3]={con[0],con[i],con[i*2%3]}; for(int j=1;j<=m;j++){ int typ=edg[j][2]%3; mat[edg[j][0]][edg[j][0]]+=w[typ]; mat[edg[j][1]][edg[j][1]]+=w[typ]; mat[edg[j][0]][edg[j][1]]-=w[typ]; mat[edg[j][1]][edg[j][0]]-=w[typ]; } res[i]=Det(); } IDFT(res); return Add(res[1].a,Add(res[2].a,res[2].a)); } int main(){ freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); Rint(n),Rint(m); for(int i=1;i<=m;i++) Rint(edg[i][0]),Rint(edg[i][1]),Rint(edg[i][2]); int ans=0; for(int tim=1;;tim=Mul(tim,3)){ ans=Add(ans,Mul(tim,Calc())); bool exi=false; for(int i=1;i<=m;i++) if(edg[i][2]/=3) exi=true; if(!exi) break; } printf("%d\n",ans); return 0; }
|