#pragma GCC target ("avx") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ALIGN __attribute__((aligned(32))) using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; template using V = vector; template using VV = V>; constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); } int bsr(int x) { return 31 - __builtin_clz(x); } int bsr(ll x) { return 63 - __builtin_clzll(x); } int bsf(int x) { return __builtin_ctz(x); } int bsf(ll x) { return __builtin_ctzll(x); } template T pow(T x, ll n, T r = 1) { while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } template struct ModInt { uint v; ModInt() : v{0} {} ModInt(ll v) : v{normS(v%MD+MD)} {} explicit operator bool() const {return v != 0;} static uint normS(const uint &x) {return (x string to_string(ModInt m) {return to_string(m.v);} using Mint = ModInt; using R = double; const R PI = 4*atan(R(1)); struct Pc { R x, y; Pc() : x(0), y(0) {} Pc(R x, R y) : x(x), y(y) {} Pc operator+(const Pc &r) const {return Pc(x+r.x, y+r.y);} Pc operator-(const Pc &r) const {return Pc(x-r.x, y-r.y);} Pc operator*(const Pc &r) const {return Pc(x*r.x-y*r.y, x*r.y+y*r.x);} Pc operator*(const R &r) const {return Pc(x*r, y*r);} Pc& operator+=(const Pc &r) {return *this=*this+r;} Pc& operator-=(const Pc &r) {return *this=*this-r;} Pc& operator*=(const Pc &r) {return *this=*this*r;} Pc& operator*=(const R &r) {return *this=*this*r;} static Pc polar(R r, R th) {return Pc(cos(th)*r, sin(th)*r);} }; void fft(bool type, vector &c) { static vector buf[30]; int N = int(c.size()); int s = bsr(N); assert(1<(N); for (int i = 0; i < N; i++) { buf[s][i] = Pc::polar(1, i*2*PI/N); } } vector a = c, b(N); for (int i = 1; i <= s; i++) { int W = 1<<(s-i); //変更後の幅W for (int y = 0; y < N/2; y += W) { Pc now = buf[s][y]; if (type) now.y *= -1; for (int x = 0; x < W; x++) { auto l = a[y<<1 | x]; auto r = now * a[y<<1 | x | W]; b[y | x] = l+r; b[y | x | N>>1] = l-r; } } swap(a, b); } c = a; } template vector multiply(vector x, vector y) { constexpr int B = 2, SHIFT = 15; int S = x.size()+y.size()-1; int N = 2< a[B], b[B]; for (int fe = 0; fe < B; fe++) { a[fe] = vector(N); b[fe] = vector(N); vector c(N); for (int i = 0; i < int(x.size()); i++) { c[i].x = (x[i].v >> (fe*SHIFT)) & ((1<> (fe*SHIFT)) & ((1< z(S); vector c[B]; for (int fe = 0; fe < B; fe++) { c[fe] = vector(N); } for (int af = 0; af < B; af++) { for (int bf = 0; bf < B; bf++) { int cf = (af+bf)%B; for (int i = 0; i < N; i++) { if (af+bf struct Poly { V v; int size() const {return int(v.size());} Poly(int N = 0) : v(V(N)) {} Poly(const V &v) : v(v) {shrink();} Poly& shrink() {while (v.size() && !v.back()) v.pop_back(); return *this;} D freq(int p) const { return (p < size()) ? v[p] : D(0); } Poly operator+(const Poly &r) const { int N = size(), M = r.size(); V res(max(N, M)); for (int i = 0; i < max(N, M); i++) res[i] = freq(i)+r.freq(i); return Poly(res); } Poly operator-(const Poly &r) const { int N = size(), M = r.size(); V res(max(N, M)); for (int i = 0; i < max(N, M); i++) res[i] = freq(i)-r.freq(i); return Poly(res); } Poly operator*(const Poly &r) const { int N = size(), M = r.size(); if (min(N, M) == 0) return Poly(); assert(N+M-1 >= 0); V res = multiply(v, r.v); return Poly(res); } Poly operator*(const D &r) const { V res(size()); for (int i = 0; i < size(); i++) res[i] = v[i]*r; return Poly(res); } Poly& operator+=(const Poly &r) {return *this = *this+r;} Poly& operator-=(const Poly &r) {return *this = *this-r;} Poly& operator*=(const Poly &r) {return *this = *this*r;} Poly& operator*=(const D &r) {return *this = *this*r;} Poly operator<<(const int n) const { assert(n >= 0); V res(size()+n); for (int i = 0; i < size(); i++) { res[i+n] = v[i]; } return Poly(res); } Poly operator>>(const int n) const { assert(n >= 0); if (size() <= n) return Poly(); V res(size()-n); for (int i = n; i < size(); i++) { res[i-n] = v[i]; } return Poly(res); } // x % y Poly rem(const Poly &y) const { return *this - y * div(y); } Poly rem_inv(const Poly &y, const Poly &ny, int B) const { return *this - y * div_inv(ny, B); } Poly div(const Poly &y) const { int B = max(size(), y.size()); return div_inv(y.inv(B), B); } Poly div_inv(const Poly &ny, int B) const { return (*this*ny)>>(B-1); } // this * this.inv() = x^n + r(x) (size()) Poly strip(int n) const { V res = v; res.resize(min(n, size())); return Poly(res); } Poly rev(int n = -1) const { V res = v; if (n != -1) res.resize(n); reverse(begin(res), end(res)); return Poly(res); } // f * f.inv() = x^B + r(x) (B >= n) Poly inv(int n) const { int N = size(); assert(N >= 1); assert(n >= N-1); Poly c = rev(); Poly d = Poly(V({D(1)/c.freq(0)})); int i; for (i = 1; i+N-2 < n; i *= 2) { auto u = V({2}); d = (d * (Poly(V{2})-c*d)).strip(2*i); } return d.rev(n+1-N); } }; template string to_string(const Poly &p) { if (p.size() == 0) return "0"; string s = ""; for (int i = 0; i < p.size(); i++) { if (p.v[i]) { s += to_string(p.v[i])+"x^"+to_string(i); if (i != p.size()-1) s += "+"; } } return s; } // x^n % mod template Poly nth_mod(ll n, const Poly &mod) { int B = mod.size() * 2 - 1; Poly mod_inv = mod.inv(B); Poly p = V{Mint(1)}; int m = (!n) ? -1 : bsr(n); for (int i = m; i >= 0; i--) { if (n & (1LL< Poly berlekamp_massey(const V &s) { int N = int(s.size()); V b = {D(1)}, c = {D(1)}; D y = D(1); for (int ed = 1; ed <= N; ed++) { int L = int(c.size()), M = int(b.size()); D x = 0; for (int i = 0; i < L; i++) { x += c[i]*s[ed-L+i]; } b.push_back(0); M++; if (!x) { continue; } D freq = x/y; if (L < M) { //use b auto tmp = c; c.insert(begin(c), M-L, D(0)); for (int i = 0; i < M; i++) { c[M-1-i] -= freq*b[M-1-i]; } b = tmp; y = x; } else { //use c for (int i = 0; i < M; i++) { c[L-1-i] -= freq*b[M-1-i]; } } } return Poly(c); } const int MD = 610 * 13; const int MC = 310; const V pd = {2, 3, 5, 7, 11, 13}; const V cd = {4, 6, 8, 9, 10, 12}; struct StopWatch { bool f = false; clock_t st; void start() { f = true; st = clock(); } int msecs() { assert(f); return (clock()-st)*1000 / CLOCKS_PER_SEC; } }; int main() { /* { V f = {1, 1, 2, 3}; cout << to_string(Poly(f)) << endl; cout << to_string(berlekamp_massey(f)) << endl; }*/ ll n; int x, y; cin >> n >> x >> y; // n = 918741897598888935; x = 298; y = 299; V co(MD+1); co[0] = 1; { int c = x; Mint buf[MC][MD]; buf[0][0] = 1; for (int d: pd) { for (int nc = 1; nc < MC; nc++) { for (int nw = d; nw < MD; nw++) { buf[nc][nw] += buf[nc-1][nw-d]; } } } V co2(MD+1); for (int i = 0; i < MD; i++) { for (int j = 0; j < MD-i; j++) { co2[i+j] += co[i]*buf[c][j]; } } co = co2; } { int c = y; Mint buf[MC][MD]; buf[0][0] = 1; for (int d: cd) { for (int nc = 1; nc < MC; nc++) { for (int nw = d; nw < MD; nw++) { buf[nc][nw] += buf[nc-1][nw-d]; } } } V co2(MD+1); for (int i = 0; i < MD; i++) { for (int j = 0; j < MD-i; j++) { co2[i+j] += co[i]*buf[c][j]; } } co = co2; } co[0] = -1; auto rco = co; reverse(begin(rco), end(rco)); auto pol = nth_mod(n, Poly(rco)); V buf(MD); buf[0] = 1; V sm(MD); for (int i = 0; i < MD; i++) { //v[i] * f for (int j = 0; j < MD; j++) { sm[j] += pol.freq(i)*buf[j]; } for (int j = 1; j < MD; j++) { buf[j] += buf[0]*co[j]; } for (int j = 0; j < MD-1; j++) { buf[j] = buf[j+1]; } buf[MD-1] = 0; } Mint ans = 0; for (int i = 0; i < MD; i++) { ans += sm[i]; } cout << ans.v << endl; return 0; }