結果
| 問題 | No.214 素数サイコロと合成数サイコロ (3-Medium) |
| ユーザー |
 LayCurse
|
| 提出日時 | 2015-05-23 01:32:05 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 22,418 bytes |
| コンパイル時間 | 1,541 ms |
| コンパイル使用メモリ | 170,592 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-07-06 05:55:19 |
| 合計ジャッジ時間 | 1,830 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
コンパイルメッセージ
main.cpp: In member function ‘unsigned int mint::setmod(unsigned int)’:
main.cpp:41:520: warning: no return statement in function returning non-void [-Wreturn-type]
41 | unsigned setmod(unsigned m){W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;}}
| ^
main.cpp: In function ‘void reader(double*)’:
main.cpp:15:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
15 | void reader(double *x){scanf("%lf",x);}
| ~~~~~^~~~~~~~~
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}
char memarr[127000000]; void *mem = memarr;
#define MD 1000000007
struct mint{
static unsigned md, W, R, Rinv, mdninv, RR;
unsigned val;
mint(){}mint(int a){val=mulR(a);}mint(unsigned a){val=mulR(a);}mint(ll a){val=mulR(a);}mint(ull a){val=mulR(a);}
unsigned setmod(unsigned m){W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;}}
unsigned mulR(unsigned a){return(ull)a*R%md;}unsigned mulR(int a){if(a<0)a=a%md+md;return mulR((unsigned)a);}unsigned mulR(ull a){return mulR((unsigned)(a%md));}unsigned mulR(ll a){if(a<0)a=a%md+md;return mulR((unsigned)a);}
unsigned reduce(unsigned T){unsigned m=T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}unsigned reduce(ull T){unsigned m=(unsigned)T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}
unsigned get(){return reduce(val);}
mint&operator+=(mint a){val+=a.val;if(val>=md)val-=md;return*this;}mint&operator-=(mint a){if(val<a.val)val=val+md-a.val;else val-=a.val;return*this;}mint&operator*=(mint a){val=reduce((ull)val*a.val);return*this;}mint&operator/=(mint a){return*this*=a.inverse();}
mint operator+(mint a){return mint(*this)+=a;}mint operator-(mint a){return mint(*this)-=a;}mint operator*(mint a){return mint(*this)*=a;}mint operator/(mint a){return mint(*this)/=a;}
mint operator+(int a){return mint(*this)+=mint(a);}mint operator-(int a){return mint(*this)-=mint(a);}mint operator*(int a){return mint(*this)*=mint(a);}mint operator/(int a){return mint(*this)/=mint(a);}
mint operator+(ll a){return mint(*this)+=mint(a);}mint operator-(ll a){return mint(*this)-=mint(a);}mint operator*(ll a){return mint(*this)*=mint(a);}mint operator/(ll a){return mint(*this)/=mint(a);}
mint operator-(void){mint res;if(val)res.val=md-val;else res.val=0;return res;}
operator bool(void){return val!=0;}operator int(void){return get();}operator ll(void){return get();}
mint inverse(){int a=val,b=md,u=1,v=0,t;mint r;while(b){t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}if(u<0)u+=md;r.val=(ull)u*RR%md;return r;}
mint pw(ull b){mint a(*this),r;r.val=R;while(b){if(b&1)r*=a;b>>=1;a*=a;}return r;}
};
unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR;
mint operator+(int a, mint b){return mint(a)+=b;}mint operator-(int a, mint b){return mint(a)-=b;}mint operator*(int a, mint b){return mint(a)*=b;}mint operator/(int a, mint b){return mint(a)/=b;}
mint operator+(ll a, mint b){return mint(a)+=b;}mint operator-(ll a, mint b){return mint(a)-=b;}mint operator*(ll a, mint b){return mint(a)*=b;}mint operator/(ll a, mint b){return mint(a)/=b;}
mint mval[10000], minv[10000];
void mint_init(int md=MD, mint val[]=mval, int vals=10000, mint inv[]=minv, int invs=10000){int i;val[0].setmod(md);val[0].val=0;REP(i,1,vals){val[i].val=val[i-1].val+mint::R;if(val[i].val >=md)val[i].val-=md;}inv[1].val=1;REP(i,2,invs){inv[i].val=md-((ll)(md/i)*inv[md%i].val%md);}REP(i,1,invs)inv[i].val=(ull)inv[i].val*mint::R%md;}
#define SSE2_M128I_ADD32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "paddd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_ADD64(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "paddq %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_SUB32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "psubd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128U_MUL32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pmuludq %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_EQ32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pcmpeqd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_GT32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pcmpgtd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_LT32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqa %%xmm0, %%xmm1;" "movdqu %2, %%xmm2;" "pcmpgtd %%xmm2, %%xmm0;" "pcmpeqd %%xmm2, %%xmm1;" "por %%xmm1, %%xmm0;" "pcmpeqd %%xmm2, %%xmm2;" "pxor %%xmm2, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1", "%xmm2");
#define SSE2_M128I_GE32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqa %%xmm0, %%xmm1;" "movdqu %2, %%xmm2;" "pcmpgtd %%xmm2, %%xmm0;" "pcmpeqd %%xmm2, %%xmm1;" "por %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1", "%xmm2");
#define SSE2_M128I_OR(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "por %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_AND(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pand %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_SHIFT_R4(c,a) asm volatile("movdqu %1, %%xmm0;" "psrldq $4, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a) :"%xmm0");
#define SSE2_M128I_SHUFFLE32_0020(c,a) asm volatile("movdqu %1, %%xmm0;" "pshufd $8, %%xmm0, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a) :"%xmm0");
#define SSE2_M128I_SHUFFLE32_0031(c,a) asm volatile("movdqu %1, %%xmm0;" "pshufd $13, %%xmm0, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a) :"%xmm0");
#define SSE2_M128I_UNPACKLO32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "punpckldq %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128U_MULLO32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "movdqa %%xmm0, %%xmm2;" "movdqa %%xmm1, %%xmm3;" "psrldq $4, %%xmm2;" "psrldq $4, %%xmm3;" "pmuludq %%xmm1, %%xmm0;" "pmuludq %%xmm3, %%xmm2;" "pshufd $8, %%xmm0, %%xmm0;" "pshufd $8, %%xmm2, %%xmm2;" "punpckldq %%xmm2, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1", "%xmm2", "%xmm3");
#define SSE4_M128U_MULLO32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pmulld %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128U_MULHI32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "movdqa %%xmm0, %%xmm2;" "movdqa %%xmm1, %%xmm3;" "psrldq $4, %%xmm2;" "psrldq $4, %%xmm3;" "pmuludq %%xmm1, %%xmm0;" "pmuludq %%xmm3, %%xmm2;" "pshufd $13, %%xmm0, %%xmm0;" "pshufd $13, %%xmm2, %%xmm2;" "punpckldq %%xmm2, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1", "%xmm2", "%xmm3");
#define SSE2_M128U_ADDMOD32(c,a,b,md) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "paddd %%xmm1, %%xmm0;" "movdqu %3, %%xmm1;" "movdqa %%xmm1, %%xmm2;" "movdqa %%xmm0, %%xmm3;" "pcmpeqd %%xmm0, %%xmm2;" "pcmpgtd %%xmm1, %%xmm3;" "por %%xmm3, %%xmm2;" "pxor %%xmm3, %%xmm3;" "pcmpgtd %%xmm0, %%xmm3;" "por %%xmm3, %%xmm2;" "pand %%xmm2, %%xmm1;" "psubd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b), "m"(md) :"%xmm0", "%xmm1", "%xmm2", "%xmm3");
#define SSE2_M128U_SUBMOD32(c,a,b,md) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "psubd %%xmm1, %%xmm0;" "movdqu %3, %%xmm1;" "pxor %%xmm2, %%xmm2;" "pcmpgtd %%xmm0, %%xmm2;" "pand %%xmm2, %%xmm1;" "paddd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b), "m"(md) :"%xmm0", "%xmm1", "%xmm2");
#define SSE4_M128U_MULMOD32M(c,a,b,md,mdninv) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm2;" "movdqa %%xmm0, %%xmm1;" "pmuludq %%xmm2, %%xmm0;" "psrldq $4, %%xmm1;" "psrldq $4, %%xmm2;" "pmuldq %%xmm2, %%xmm1;" "pshufd $8, %%xmm0, %%xmm2;" "pshufd $8, %%xmm1, %%xmm3;" "punpckldq %%xmm3, %%xmm2;" "pmulld %4, %%xmm2;" "movdqu %3, %%xmm4;" "movdqa %%xmm2, %%xmm3;" "pmuludq %%xmm4, %%xmm2;" "psrldq $4, %%xmm3;" "pmuludq %%xmm4, %%xmm3;" "paddq %%xmm0, %%xmm2;" "paddq %%xmm1, %%xmm3;" "pshufd $13, %%xmm2, %%xmm2;" "pshufd $13, %%xmm3, %%xmm3;" "punpckldq %%xmm3, %%xmm2;" "movdqa %%xmm4, %%xmm3;" "movdqa %%xmm2, %%xmm0;" "pcmpeqd %%xmm0, %%xmm3;" "pcmpgtd %%xmm4, %%xmm0;" "por %%xmm3, %%xmm0;" "pxor %%xmm3, %%xmm3;" "pcmpgtd %%xmm2, %%xmm3;" "por %%xmm3, %%xmm0;" "pand %%xmm4, %%xmm0;" "psubd %%xmm0, %%xmm2;" "movdqu %%xmm2, %0;" :"=m"(c) :"m"(a), "m"(b), "m"(md), "m"(mdninv) :"%xmm0", "%xmm1", "%xmm2", "%xmm3", "%xmm4");
#define TO_MY128(a) (*(MY128*)(a))
union MY128{
int M32I[4];
unsigned M32U[4];
MY128(){
}
MY128(int a, int b, int c, int d){
M32I[0] = a;
M32I[1] = b;
M32I[2] = c;
M32I[3] = d;
}
MY128(unsigned a, unsigned b, unsigned c, unsigned d){
M32U[0] = a;
M32U[1] = b;
M32U[2] = c;
M32U[3] = d;
}
MY128(int a){
M32I[0] = a;
M32I[1] = a;
M32I[2] = a;
M32I[3] = a;
}
MY128(unsigned a){
M32U[0] = a;
M32U[1] = a;
M32U[2] = a;
M32U[3] = a;
}
MY128(MY128 *mem){
__asm__ volatile("movdqu %1, %0;" :"=m"(*this) :"m"(*mem));
}
void set(int a, int b, int c, int d){
M32I[0] = a;
M32I[1] = b;
M32I[2] = c;
M32I[3] = d;
}
void set(unsigned a, unsigned b, unsigned c, unsigned d){
M32U[0] = a;
M32U[1] = b;
M32U[2] = c;
M32U[3] = d;
}
void set(int a){
M32I[0] = a;
M32I[1] = a;
M32I[2] = a;
M32I[3] = a;
}
void set(unsigned a){
M32U[0] = a;
M32U[1] = a;
M32U[2] = a;
M32U[3] = a;
}
void set(MY128 *mem){
__asm__ volatile("movdqu %1, %0;" :"=m"(*this) :"m"(*mem));
}
void get(MY128 *mem){
__asm__ volatile("movdqu %1, %0;" :"=m"(*mem) :"m"(*this));
}
MY128& operator=(MY128 a){
__asm__ volatile("movdqu %1, %0;" :"=m"(*this) :"m"(a));
return *this;
}
} __attribute__((aligned(16)));
void mfft(int n, mint x[], mint root, void *mem){
int i, j, k;
int n1, n2, n3, step = 1;
mint w1, w2, w3, a, b, c, d, aa, bb, cc, dd, tmp, *y = (mint*)mem;
MY128 A, B, C, D, AA, BB, CC, DD, md, t1, t2, mask, TMP, W1, W2, W3, MDNINV;
MY128 *tt;
tmp = root.pw((mint::md-1)/4*3);
root = root.pw((mint::md-1)/n);
md.set(mint::md);
TMP.set(tmp.val);
MDNINV.set(mint::mdninv);
while(n > 2){
n1 = n / 4;
n2 = n1 + n1;
n3 = n1 + n2;
w1.val = mint::R;
rep(i,n1){
w2 = w1*w1;
w3 = w1*w2;
W1.set(w1.val);
W2.set(w2.val);
W3.set(w3.val);
for(j=0;j+3<step;j+=4){
SSE2_M128U_ADDMOD32(AA, x[j+step*i], x[j+step*(i+n2)], md);
SSE2_M128U_SUBMOD32(BB, x[j+step*i], x[j+step*(i+n2)], md);
SSE2_M128U_ADDMOD32(CC, x[j+step*(i+n1)], x[j+step*(i+n3)], md);
SSE2_M128U_SUBMOD32(DD, x[j+step*(i+n1)], x[j+step*(i+n3)], md);
SSE4_M128U_MULMOD32M(DD, DD, TMP, md, MDNINV);
SSE2_M128U_ADDMOD32(y[j+step*(4*i )], AA, CC, md);
SSE2_M128U_SUBMOD32(B, BB, DD, md);
SSE4_M128U_MULMOD32M(y[j+step*(4*i+1)], W1, B, md, MDNINV);
SSE2_M128U_SUBMOD32(C, AA, CC, md);
SSE4_M128U_MULMOD32M(y[j+step*(4*i+2)], W2, C, md, MDNINV);
SSE2_M128U_ADDMOD32(D, BB, DD, md);
SSE4_M128U_MULMOD32M(y[j+step*(4*i+3)], W3, D, md, MDNINV);
}
REP(j,j,step){
a = x[j+step*i];
b = x[j+step*(i+n1)];
c = x[j+step*(i+n2)];
d = x[j+step*(i+n3)];
aa = a + c;
bb = a - c;
cc = b + d;
dd = (b - d) * tmp;
y[j+step*(4*i )] = aa + cc;
y[j+step*(4*i+1)] = w1*(bb - dd);
y[j+step*(4*i+2)] = w2*(aa - cc);
y[j+step*(4*i+3)] = w3*(bb + dd);
}
w1 *= root;
}
n /= 4;
step *= 4;
root *= root;
root *= root;
swap(x,y);
}
if(n==2){
for(i=0;i+3<step;i+=4){
SSE2_M128U_ADDMOD32(y[i], x[i], x[i+step], md);
SSE2_M128U_SUBMOD32(y[i+step], x[i], x[i+step], md);
}
REP(i,i,step){
y[i] = x[i] + x[i+step];
y[i+step] = x[i] - x[i+step];
}
n /= 2;
step *= 2;
root *= root;
swap(x,y);
}
rep(i,step) y[i] = x[i];
}
void mfftinv(int n, mint x[], mint root, void *mem){
int i, j;
int n1, n2, n3, step = 1;
mint w1, w2, w3, a, b, c, d, aa, bb, cc, dd, tmp, *y = (mint*)mem;
MY128 A, B, C, D, AA, BB, CC, DD, md, t1, t2, mask, TMP, W1, W2, W3, MDNINV;
root = root.inverse();
tmp = root.pw((mint::md-1)/4);
root = root.pw((mint::md-1)/n);
md.set(mint::md);
TMP.set(tmp.val);
MDNINV.set(mint::mdninv);
while(n > 2){
n1 = n / 4;
n2 = n1 + n1;
n3 = n1 + n2;
w1.val = mint::R;
rep(i,n1){
w2 = w1*w1;
w3 = w1*w2;
W1.set(w1.val);
W2.set(w2.val);
W3.set(w3.val);
for(j=0;j+3<step;j+=4){
SSE2_M128U_ADDMOD32(AA, x[j+step*i], x[j+step*(i+n2)], md);
SSE2_M128U_SUBMOD32(BB, x[j+step*i], x[j+step*(i+n2)], md);
SSE2_M128U_ADDMOD32(CC, x[j+step*(i+n1)], x[j+step*(i+n3)], md);
SSE2_M128U_SUBMOD32(DD, x[j+step*(i+n1)], x[j+step*(i+n3)], md);
SSE4_M128U_MULMOD32M(DD, DD, TMP, md, MDNINV);
SSE2_M128U_ADDMOD32(y[j+step*(4*i )], AA, CC, md);
SSE2_M128U_ADDMOD32(B, BB, DD, md);
SSE4_M128U_MULMOD32M(y[j+step*(4*i+1)], W1, B, md, MDNINV);
SSE2_M128U_SUBMOD32(C, AA, CC, md);
SSE4_M128U_MULMOD32M(y[j+step*(4*i+2)], W2, C, md, MDNINV);
SSE2_M128U_SUBMOD32(D, BB, DD, md);
SSE4_M128U_MULMOD32M(y[j+step*(4*i+3)], W3, D, md, MDNINV);
}
REP(j,j,step){
a = x[j+step*i];
b = x[j+step*(i+n1)];
c = x[j+step*(i+n2)];
d = x[j+step*(i+n3)];
aa = a + c;
bb = a - c;
cc = b + d;
dd = (b - d) * tmp;
y[j+step*(4*i )] = aa + cc;
y[j+step*(4*i+1)] = w1*(bb + dd);
y[j+step*(4*i+2)] = w2*(aa - cc);
y[j+step*(4*i+3)] = w3*(bb - dd);
}
w1 *= root;
}
n /= 4;
step *= 4;
root *= root;
root *= root;
swap(x,y);
}
if(n==2){
for(i=0;i+3<step;i+=4){
SSE2_M128U_ADDMOD32(y[i], x[i], x[i+step], md);
SSE2_M128U_SUBMOD32(y[i+step], x[i], x[i+step], md);
}
REP(i,i,step){
y[i] = x[i] + x[i+step];
y[i+step] = x[i] - x[i+step];
}
n /= 2;
step *= 2;
root *= root;
swap(x,y);
}
rep(i,step) y[i] = x[i];
}
void gmodcomvolutionsGetData(int num, int md[], int root[], int inv[]){int i,j,k;static int A[5]={1004535809,1007681537,1012924417,1045430273,1051721729},B[5]={3,3,5,3,6},C[5][5]={{},{335894166},{253231225,405169960},{26805930,551754894,843088962},{303830744,325532940,568498259,175287122}};rep(i,num)md[i]=A[i];rep(i,num)root[i]=B[i];rep(i,num)rep(j,i)inv[i*num+j]=C[i][j];}
template<class S, class T, class U> void gmodconvolution(S A[], int As, T B[], int Bs, U res[], int Rs, void *mem, int md, int num=3){int i,j,k,m,n,q,*x,*y,*z,*w;mint r,R,**a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);n=max(As+Bs,Rs);for(q=1;q<n;q*=2);a=(mint**)(z+num*num);a[0]=(mint*)(a+num+1);REP(i,1,num+1)a[i]=a[i-1]+q;mem=a[num]+q;rep(j,num){r.setmod(x[j]);rep(i,As)a[j][i]=A[i];rep(i,Bs)a[num][i]=B[i];REP(i,As,q)a[j][i].val=0;REP(i,Bs,q)a[num][i].val=0;R=y[j];mfft(q,a[j],R,mem);mfft(q,a[num],R,mem);rep(i,q)a[j][i]*=a[num][i];r=mint(q).inverse();mfftinv(q,a[j],R,mem);rep(i,Rs)a[j][i]*=r;rep(i,Rs)a[j][i].val=a[j][i].get();}r.setmod(md);rep(m,Rs){rep(i,num)w[i]=a[i][m].val;rep(i,num)rep(j,i){k=w[i]-w[j];if(k<0)k+=x[i];w[i]=(ll)k*z[i*num+j]%x[i];}k=0;for(i=num-1;i>=0;i--)k=((ll)k*x[i]+w[i])%md;res[m]=k;}}
template<class S, class T> void gmodconvolution(S A[], int As, T res[], int Rs, void *mem, int md, int num=3){int i,j,k,m,n,q,*x,*y,*z,*w;mint r,R,**a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);n=max(As+As,Rs);for(q=1;q<n;q*=2);a=(mint**)(z+num*num);a[0]=(mint*)(a+num);REP(i,1,num)a[i]=a[i-1]+q;mem=a[num-1]+q;rep(j,num){r.setmod(x[j]);rep(i,As)a[j][i]=A[i];REP(i,As,q)a[j][i].val=0;R=y[j];mfft(q,a[j],R,mem);rep(i,q)a[j][i]*=a[j][i];r=mint(q).inverse();mfftinv(q,a[j],R,mem);rep(i,Rs)a[j][i]*=r;rep(i,Rs)a[j][i].val=a[j][i].get();}r.setmod(md);rep(m,Rs){rep(i,num)w[i]=a[i][m].val;rep(i,num)rep(j,i){k=w[i]-w[j];if(k<0)k+=x[i];w[i]=(ll)k*z[i*num+j]%x[i];}k=0;for(i=num-1;i>=0;i--)k=((ll)k*x[i]+w[i])%md;res[m]=k;}}
template<class S> void gmodconvolutionPreCalc(S A[], int As, mint res[], int Rs, void *mem, int md, int num=3, int domultiply=1){int i,j,q,*x,*y,*z,*w;mint r,R,*a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);q=Rs;a=(mint*)(z+num*num);mem=a+q;rep(j,num){r.setmod(x[j]);rep(i,As)a[i]=A[i];REP(i,As,q)a[i].val=0;R=y[j];mfft(q,a,R,mem);rep(i,Rs)res[j*Rs+i]=a[i];if(domultiply){r=mint(q).inverse();rep(i,Rs)res[j*Rs+i]*=r;}}r.setmod(md);}
template<class T, class U> void gmodconvolutionWithPreCalc(mint A[], int As, T B[], int Bs, U res[], int Rs, void *mem, int md, int num=3, int ordered=1, int domultiply=0){int i,j,q,k,m,*x,*y,*z,*w;mint r,R,**a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);q=As;a=(mint**)(z+num*num);a[0]=(mint*)(a+num+1);REP(i,1,num+1)a[i]=a[i-1]+q;mem=a[num]+q;rep(j,num){r.setmod(x[j]);rep(i,q)a[j][i]=A[j*q+i];rep(i,Bs)a[num][i]=B[i];REP(i,Bs,q)a[num][i].val=0;R=y[j];mfft(q,a[num],R,mem);rep(i,q)a[j][i]*=a[num][i];mfftinv(q,a[j],R,mem);if(domultiply){r=mint(q).inverse();rep(i,Rs)a[j][i]*=r;}rep(i,Rs)a[j][i].val=a[j][i].get();}r.setmod(md);rep(m,Rs){rep(i,num)w[i]=a[i][m].val;rep(i,num)rep(j,i){k=w[i]-w[j];if(k<0)k+=x[i];w[i]=(ll)k*z[i*num+j]%x[i];}k=0;for(i=num-1;i>=0;i--)k=((ll)k*x[i]+w[i])%md;res[m]=k;}}
int modconvolutionGetLength(int As, int Bs, int Rs){int n=max(As+Bs,Rs),res;for(res=1;res<n;res*=2);return res;}
template<class T> void Kitamasa_mg_reduce(int a[], int y, T c[], int d, int md, ll L, int h, int o, mint **calc, int *q, int *p, void *mem){int i,j,t,l,E,*D=(int*)mem;ll*Z=(ll*)(D+2*d);mem=(void*)(Z+y);rep(i,y)Z[i]=a[i];for(j=o-1;j>=0;j--){E=y-d;l=q[j]-d;if(E<2*l)continue;t=E-2*l;gmodconvolutionWithPreCalc(calc[j],p[j],Z+y-l,l,D,d+l,mem,md,h);rep(i,d+l){Z[t+i+1]+=D[i];if(Z[t+i]>=md)Z[t+i]-=md;}y-=l;}while(y>d){y--;if(Z[y]>=md)Z[y]%=md;rep(i,d){Z[y-d+i]+=Z[y]*(ll)c[i];if(Z[y-d+i]>=L)Z[y-d+i]%=md;}}rep(i,y)if(Z[i]>=md)Z[i]%=md;rep(i,y)a[i]=Z[i];}
template<class S, class T> ll Kitamasa_mg(ll n, S a[], T c[], int d, int md, void *mem){int i,j,m,l,t,y,s,*A,*D,*E,o=0,*R,*W,h;mint **Q;ll L=((1ULL<<63)-1)-(ull)(md-1)*(md-1),*Z,C;if(n<d)return a[n];h=ceil((log(2)+log(d)+2*log(md))/log(1004535809)+1e-5);R=(int*)mem;W=R+25;Q=(mint**)(W+25);A=(int*)(Q+25);mem=A+2*d;for(i=20;i>=0;i--)if(d/(1<<i)>=500||i==0){m=d+d/(1<<i);rep(j,m)A[j]=0;A[m-1]=1;Kitamasa_mg_reduce(A,m,c,d,md,L,h,o,Q,R,W,mem);R[o]=m;l=m-d;W[o]=modconvolutionGetLength(d,l,d+l);Q[o]=(mint*)mem;mem=Q[o]+W[o]*h;gmodconvolutionPreCalc(A,d,Q[o],W[o],mem,md,h);o++;}Z=(ll*)mem;y=0;for(;;){Z[y++]=n;if(n<2*d)break;n/=2;}D=(int*)(Z+y);E=D+4*d;mem=E+2*d;rep(i,2*d)A[i]=0;A[Z[--y]]=1;while(y--){gmodconvolution(A,2*d,D,4*d,mem,md,h);s=4*d;j=o-1;rep(m,2){l=R[j]-d;t=s-d-2*l;gmodconvolutionWithPreCalc(Q[j],W[j],D+s-l,l,E,d+l,mem,md,h);rep(i,d+l){D[t+i+1]+=E[i];if(D[t+i+1]>=md)D[t+i+1]-=md;}s-=l;}rep(i,2*d)A[i]=D[i];if(Z[y]!=Z[y+1]*2){C=A[2*d-1];for(i=2*d-1;i;i--)A[i]=A[i-1]; A[0]=0;rep(i,d)A[d+i]=(A[d+i]+(ll)c[i]*C)%md;}}Kitamasa_mg_reduce(A,2*d,c,d,md,L,h,o,Q,R,W,mem);C=0;rep(i,d){C+=(ll)a[i]*A[i];if(C>=L)C%=md;}if(C>=md)C%=md;return C;}
int pp[6] = {2,3,5,7,11,13};
int cc[6] = {4,6,8,9,10,12};
mint dp_p[301][4200], dp_c[301][4200];
mint a[9400], c[9400];
int aaa[9400], ccc[9400];
int main(){
int i, j, k, d;
ll N; int P, C;
int res;
mint_init();
dp_p[0][0] = dp_c[0][0] = mval[1];
rep(k,6) rep(i,50) rep(j,700) if(dp_p[i][j]) dp_p[i+1][j+pp[k]] += dp_p[i][j];
rep(k,6) rep(i,50) rep(j,700) if(dp_c[i][j]) dp_c[i+1][j+cc[k]] += dp_c[i][j];
reader(&N);
reader(&P, &C);
d = P * pp[5] + C * cc[5];
rep(i,d) a[i] = mval[1];
rep(i,700) if(dp_p[P][i]) rep(j,700) if(dp_c[C][j]) c[d-i-j] += dp_p[P][i] * dp_c[C][j];
rep(i,d) aaa[i]=(int)a[i];
rep(i,d) ccc[i]=(int)c[i];
res = Kitamasa_mg(N+d-1, aaa, ccc, d, MD, mem);
writer(res, '\n');
return 0;
}