#pragma GCC optimize("O3") #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma GCC optimize("Ofast") #include using namespace std; using ll = long long; using poly = vector; const long long int MOD = 1e9 + 7; long long int dp[2][51][651]; long long int c[1251]; vector a = {2,3,5,7,11,13}; vector b = {4,6,8,9,10,12}; long long int n,p,q; vector v; long long int dp2[1251]; int Mod(ll x){ return (x %= MOD) < 0 ? x + MOD : x; } poly Mul(const poly &a, const poly &b){ poly ret(a.size() + b.size() - 1); for(int i=0; i=b.size()-1; i--) for(int j=0; j>= 1; xn = Div(Mul(xn, xn), f); } ll ret = 0; for(int i=0; i> n >> p >> q; int m = p*a[5] + q*b[5]; dp[0][0][0] = 1; dp[1][0][0] = 1; for(int i=0;i=0;j--) { for(int k=0;k<=p*a[5];k++) { if(dp[0][j][k]==0) continue; for(int l=j+1;l<=p;l++) { if(k + (l-j)*a[i] > p*a[5]) break; dp[0][l][k + (l-j)*a[i]] += dp[0][j][k]; dp[0][l][k + (l-j)*a[i]]%=MOD; } } } } for(int i=0;i=0;j--) { for(int k=0;k<=q*b[5];k++) { if(dp[1][j][k]==0) continue; for(int l=j+1;l<=q;l++) { if(k + (l-j)*b[i] > q*b[5]) break; dp[1][l][k + (l-j)*b[i]] += dp[1][j][k]; dp[1][l][k + (l-j)*b[i]]%=MOD; } } } } for(int i=0;i<=p*a[5];i++) { for(int j=0;j<=q*b[5];j++) { if(i+j > m) continue; c[i+j] += ((dp[0][p][i]*dp[1][q][j])%MOD); c[i+j]%=MOD; } } dp2[0] = 1; for(int i=0;i<=m;i++) { for(int j=0;j<=m;j++) { if(i+j > m) break; dp2[i+j] += ((dp2[i]*c[j])%MOD); dp2[i+j]%=MOD; } } poly A,C; for(int i=0;i<=m;i++) { A.push_back(dp2[i]); } for(int i=m;i>0;i--) { C.push_back(c[i]); } long long int res = 0; long long int L = n - m; if(L < 0) L = 0; long long int R = n - 1; for(long long int i=L;i<=R;i++) { long long int val = kitamasa(C,A,i); for(int j=0;j<=m;j++) { if(i+j >= n) { res += ((val*c[j])%MOD); res%=MOD; } } } cout << res << '\n'; return 0; }