using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ int[] PDice=new int[]{2,3,5,7,11,13}; int[] CDice=new int[]{4,6,8,9,10,12}; int mod=(int)1e9+7; int ii,jj,kk; // dpP[n][val]:n回の出目でvalになる組み合わせ int[][] dpP=new int[P+1][]; for(int i=0;i<=P;i++){ dpP[i]=new int[13*P+1]; } dpP[0][0]=1; for(int i=0;i=dpP[j+1].Length){kk++;continue;} dpP[j+1][kk+PDice[i]]+=xx; if(dpP[j+1][kk+PDice[i]]>=mod)dpP[j+1][kk+PDice[i]]-=mod; kk++; } } } // dpC[n][val]:n回の出目でvalになる組み合わせ int[][] dpC=new int[C+1][]; for(int i=0;i<=C;i++){ dpC[i]=new int[12*C+1]; } dpC[0][0]=1; for(int i=0;i=dpC[j+1].Length){kk++;continue;} dpC[j+1][kk+CDice[i]]+=xx; if(dpC[j+1][kk+CDice[i]]>=mod)dpC[j+1][kk+CDice[i]]-=mod; kk++; } } } // P,C個の組み合わせ:1回振って出る出目の組み合わせ int MaxLen=13*P+12*C; long[] Throw=new long[MaxLen+1]; //for(int i=0;i<=13*P;i++){ //for(int j=0;j<=12*C;j++){ ii=0; foreach(var xi in dpP[P]){ jj=0; foreach(var xj in dpC[C]){ Throw[ii+jj]+=xi*xj; if(Throw[ii+jj]>=mod)Throw[ii+jj]%=mod; jj++; } ii++; } // // C[k]をk番目のマスに来る組み合わせとして、0番目のマスからN-1番目のマスまで順次サイコロを振っていく様子を考える。 //  ・kマスからk+tマスに動く組み合わせは C[k]*Throw[t] だけあるので //   kマスでサイコロを振ると、C[k+j] (j=1,2,…,13*P+12*C)にC[k]*Throw[j]だけ足されていく。 //  ・C[0]==1 // //  (簡潔化のため出目の最大値=3、Throw[1]=a,Throw[2]=b,Throw[3]=c とし、N=5とすると //   //   Turn 0 1 2 3 4 5 6 7 (マス) // 0 C[*] 1(=C0) // 1 C[*] C0*a C0*b C0*c // (=C1) // 2 C[*] C0*b+C1*a C0*c+C1*b C1*c // (=C2) // 3 C[*] C0*c+C1*b+C2*a C1*c+C2*b C2*c // (=C3) // 4 C[*] C1*c+C2*b+C3*a C2*c+C3*b C3*c // (=C4) // 5 C[*] C2*c+C3*b+C4*a C3*c+C4*b C4*c // // この時点で全ての場合においてN>=5にゴールしているので、ここで和を取る。(C2*c+C3*b+C4*a + C3*c+C4*b + C4*c) // //  ・ここで係数だけみると、 多項式 T^7 を 多項式 T^3-(a*T^2+b*T^1+c*T^0) で筆算で割り算しているのと同じという事がわかる。 //   (最後に余りの係数の総和をとる) //  ・ということで、元の問題は 多項式 T^(N+(出目の最大値)-1) を 多項式 ΣThrow[k]*T^k で割って、余りを求めればよい。 // kitamasa(O(d^2 Log N)) long[] rel=new long[MaxLen]; for(int i=0;imod)ret-=mod; } Console.WriteLine(ret); } long N; int P,C; public Sol(){ var ss=rsa(); N=long.Parse(ss[0]); P=int.Parse(ss[1]); C=int.Parse(ss[2]); } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(){return Console.ReadLine().Split(' ');} static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));} static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));} static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));} } class ModPolynomial_m{ //Kitamasa method (naive convolution/naive reduction); int K; long[] Rel; long mod; public ModPolynomial_m(long[] rel,long mod_){ // usage: ak=rel[0]*a0+...+rel[k-1]*a(k-1); // T^k=rel[0]*1+rel[1]*T^1+...+rel[k-1]*T^(k-1); Rel=new long[rel.Length]; K=Rel.Length; for(int i=0;imod)ret[i+j]%=mod; j++; } i++; } return ret; } public long[] Reduction_m(long[] a){ // reduce with Relation a(k)=rel[0]*a0+...+rel[k-1]*a(k-1); if(a.Length<=K)return a; int N=a.Length; int j; //long[] ret0=(long[])a.Clone(); long[] ret0=new long[a.Length]; //for(int i=0;i=K;i--){ if(ret0[i]==0)continue; //for(int j=0;jmod)ret0[i-K+j]%=mod; j++; } } long[] ret=new long[K]; for(int i=0;i0){ if((k&1)==1){ ret=Reduction_m( Convolution_m( ret,x )); } k>>=1; x=Reduction_m( Convolution_m( x,x )); } return ret; } /* b0:(a0,a1,a2)->a0 b0=(1,0,0); b0:(a1,a2,a3)->a1 b1:(a0,a1,a2)->a1 b1=(0,1,0); b0:(a2,a3,a4)->a2 b1:(a1,a2,a3)->a2 b2:(a0,a1,a2)->a2 b2=(0,0,1); b0:(a3,a4,a5)->a3 b1:(a2,a3,a4)->a3 b2:(a1,a2,a3)->a3 b3:(a0,a1,a2)->a3 b3=(0,0,0,1)=(1,1,1) <=> a3=a2+a1+a0; <=> t^3 mod t^3-t^2-t^1-1 = t^2+t^1+1 b0:(a4,a5,a6)->a4 b1:(a3,a4,a5)->a4 b2:(a2,a3,a4)->a4 b3:(a1,a2,a3)->a4 b4:(a0,a1,a2)->a4 b4=(0.0,0,0,1)=(0,1,1,1)=(1,2,2) <=> a4=a1+a2+a3=a0+2*a1+2*a2 <=> t^4 mod t^3-t^2-t^1-1 == t^3+t^2+t^1 == 2*t^2+2*t^1+1 b(x+y)=b(1+...+1+1+...+1)=b1*...*b1*b1*...*b1=b(1+...+1)*b(1+...+1)=bx*by */ }