#include #include #include #include #include using namespace std; vector pattern; class Kitamasa{ private: vector C; // a[n+1] = C[0] a[n] + C[1] a[n-1]+...C[S-1] a[n-S+1] (n=0,1,...) int mod; public: Kitamasa(vector p){ C=p;mod=1000000007; } vector mul(vector u, vector v){ // a[x] = (u[0] a[S-1] + u[1] a[S-2] +, ... + u[S-1] a[0]) // a[y] = (v[0] a[S-1] + v[1] a[S-2] +, ... + v[S-1] a[0]) // our purpose is to calculate w such that // a[x+y] = (w[0] a[S-1] + w[1] a[S-2] +, ... + w[S-1] a[0]) // a[x+y] = (u[0]a[y+S-1]+u[1]a[y+S-2]+...+u[S-1]a[y]) // = (u[0](v[0]a[2S-2]+v[1]a[2S-3]+...+v[S-1]a[S-1]) // +u[1](v[0]a[2S-3]+v[1]a[2S-4]+...+v[S-1]a[S-2]) // +...) // = sum(u[i]v[j]a[k]) where 0<=i,j<=S-1, i+j+k=2S-2 int S=u.size(); vector ret(2*S-1,0); for( int i = 0 ; i < S; i++){ for( int j=0;j=S; i--){ for( int j = 0 ; j < S; j++){ ret[i-1-j]=(1LL*ret[i-1-j]+ret[i]*1LL*C[j])%mod; } } ret.resize(S); reverse(ret.begin(),ret.end()); return ret; } }; int main(){ long long N; int P,C; cin>>N>>P>>C; int T=P*13+C*12+1; int dp[T][P+1][6]; int dp2[T][C+1][6]; int pdice[]={2,3,5,7,11,13}; int cdice[]={4,6,8,9,10,12}; memset(dp,0,sizeof(dp)); memset(dp2,0,sizeof(dp2)); dp[0][0][0]=1; for( int i=1 ; i<=P; i++ )for( int j=0;j=0)dp[j][i][k]+=dp[j-pdice[k]][i-1][l]; } } for(int i=0;i=0)dp2[j][i][k]+=dp2[j-cdice[k]][i-1][l]; } } pattern=vector(T,0); for(int i=0;i=0,p[i]=pattern[i+1]) // initial value: a[0]=1,a[-1]=1,a[-2]=1,.... # to regard a[n] as num of the way to over n // a[1] = p[0]a[0]+ p[1]a[-1]+....p[S-1]a[-S+1] // let's denote coefficients as v[1]=(p[0],...,p[S-1]) // a[2] = p[0]a[1]+ p[1]a[0]+....p[S-1]a[-S+2] // = (p[1]+p[0]^2)a[0]+(p[2]+p[1]p[0])a[1]...(p[S-1]+p[S-2]p[0])a[-S+2]+p[S-1]a[-S+1] // this can be described as v[2]=(p[1]+p[0]^2,...,p[-S+2]+p[-S+1]p[0],p[S-1]) // Now, let's calculate v[N] with initial value is a[0]=a[-1]=a[-2]=...=a[-S+1]=1 // this can be regarded as calculate V[N+S-1] with initial value A[S-1]=...=A[0]=1 // note that V[0]=v[-S+1]=(0,0,0,...,1), V[1]=(0,0,0,...,1,0); int EXP=N+S-1; vector v(S,0); for( int i =0 ; i < S; i++ ){ v[i]=pattern[i+1]; cout << v[i] <<", "; } cout << endl; long long ans = 0; int mod=1000000007; Kitamasa ktms(v); vector a(S,0); vector b(S,0); a[S-1]=1; b[S-2]=1; cout << EXP << endl; int off=1; int cnt=0; while( EXP > 0 ){ if( EXP%2==1 ){ cnt+=off; a=ktms.mul(a,b); /* cout << cnt<<": "; for( int i =0 ; i < S; i++ ){ cout << a[i]<<"+";} cout << endl; */ } off*=2; b=ktms.mul(b,b); /* cout << off<<": "; for( int i =0 ; i < S; i++ ){ cout << b[i]<<"+";} cout << endl; */ EXP/=2; } for( int i = 0 ; i