結果
問題 | No.2013 Can we meet? |
ユーザー |
![]() |
提出日時 | 2022-07-16 13:59:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 238 ms / 2,500 ms |
コード長 | 25,951 bytes |
コンパイル時間 | 2,523 ms |
コンパイル使用メモリ | 193,696 KB |
実行使用メモリ | 10,140 KB |
最終ジャッジ日時 | 2024-06-28 13:33:09 |
合計ジャッジ時間 | 6,903 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2022.07.16 13:59:08**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template< int MOD >struct mint {public:unsigned int x;mint() : x(0) {}mint(long long v) {long long w = (long long)(v % (long long)(MOD));if (w < 0) w += MOD;x = (unsigned int)(w);}mint(std::string &s) {unsigned int z = 0;for (int i = 0; i < s.size(); i++) {z *= 10;z += s[i] - '0';z %= MOD;}x = z;}mint operator+() const { return *this; }mint operator-() const { return mint() - *this; }mint& operator+=(const mint &a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}mint& operator-=(const mint &a) {if ((x -= a.x) >= MOD) x += MOD;return *this;}mint& operator*=(const mint &a) {unsigned long long z = x;z *= a.x;x = (unsigned int)(z % MOD);return *this;}mint& operator/=(const mint &a) {return *this = *this * a.inv(); }friend mint operator+(const mint& lhs, const mint& rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs) {return lhs.x == rhs.x;}friend bool operator!=(const mint& lhs, const mint& rhs) {return lhs.x != rhs.x;}friend std::ostream& operator<<(std::ostream &os, const mint &n) {return os << n.x;}friend std::istream &operator>>(std::istream &is, mint &n) {unsigned int x;is >> x;n = mint(x);return is;}mint inv() const {assert(x);return pow(MOD-2);}mint pow(long long n) const {assert(0 <= n);mint p = *this, r = 1;while (n) {if (n & 1) r *= p;p *= p;n >>= 1;}return r;}mint sqrt() const {if (this->x < 2) return *this;if (this->pow((MOD-1)>>1).x != 1) return mint(0);mint b = 1, one = 1;while (b.pow((MOD-1) >> 1) == 1) b += one;long long m = MOD-1, e = 0;while (m % 2 == 0) m >>= 1, e += 1;mint x = this->pow((m - 1) >> 1);mint y = (*this) * x * x;x *= (*this);mint z = b.pow(m);while (y.x != 1) {int j = 0;mint t = y;while (t != one) j += 1, t *= t;z = z.pow(1LL << (e-j-1));x *= z; z *= z; y *= z; e = j;}return x;}};constexpr int MOD = 998244353;template < const int MOD , bool any = false>struct FormalPowerSeries {private:using FPS = FormalPowerSeries<MOD,any>;void ntt(bool inverse) {static bool first = true;static mint<MOD> dw[30], idw[30];if (first) {first = false;mint<MOD> root = 2;while (root.pow((MOD - 1) / 2) == 1) root += 1;for (int i = 0; i < 30; i++) dw[i] = -root.pow((MOD - 1) >> (i + 2)), idw[i] = mint<MOD>(1) / dw[i];}int n = this->size();assert((n & (n - 1)) == 0);if (not inverse) {for (int m = n; m >>= 1;) {mint<MOD> w = 1;for (int s = 0, k = 0; s < n; s += 2 * m) {for (int i = s, j = s + m; i < s + m; i++, j++) {auto x = this->a[i], y = this->a[j]*w;if (x.x >= MOD) x.x -= MOD;this->a[i].x = x.x + y.x, this->a[j].x = x.x+(MOD-y.x);}w *= dw[__builtin_ctz(++k)];}}} else {for (int m = 1; m < n; m *= 2) {mint<MOD> w = 1;for (int s = 0, k = 0; s < n; s += 2 * m) {for (int i = s, j = s + m; i < s + m; i++, j++) {auto x = this->a[i], y = this->a[j];this->a[i] = x+y, this->a[j].x = x.x+(MOD-y.x), this->a[j] *= w;}w *= idw[__builtin_ctz(++k)];}}}auto c = mint<MOD>(1) / mint<MOD>(inverse ? n : 1);for (auto&& e : this->a) e *= c;}FPS convolution_naive(FPS &a, FPS &b) const {int n = int(a.size()), m = int(b.size());FPS ans(n+m-1);if (n < m) {for (int j = 0; j < m; j++) {for (int i = 0; i < n; i++) ans[i + j] += a[i]*b[j];}}else {for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) ans[i + j] += a[i]*b[j];}}return ans;}FPS& convolution_inplace(FPS b) {if (this->size() == 0 || b.size() == 0) {this->a.clear();return *this;}if (!any) {int n = this->size(), m = b.size(), sz = 1 << __lg(2*(n+m-1)-1);if (min(n, m) <= 60) return *this = convolution_naive(*this,b);this->resize(sz), this->ntt(false);b.resize(sz), b.ntt(false);for (int i = 0; i < sz; i++) this->a[i] *= b[i];this->ntt(true), this->resize(n + m - 1);return *this;}else {int n = this->a.size(), m = b.a.size();static constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617;FormalPowerSeries< mod0 > l0(n), r0(m);FormalPowerSeries< mod1 > l1(n), r1(m);FormalPowerSeries< mod2 > l2(n), r2(m);for (int i = 0; i < n; i++) l0.a[i] = this->a[i].x, l1.a[i] = this->a[i].x, l2.a[i] = this->a[i].x;for (int j = 0; j < m; j++) r0.a[j] = b.a[j].x, r1.a[j] = b.a[j].x, r2.a[j] = b.a[j].x;l0 *= r0;l1 *= r1;l2 *= r2;crt(*this,l0,l1,l2);return *this;}}template<const int MOD0, const int MOD1, const int MOD2>static void crt(FPS &fps,const FormalPowerSeries<MOD0> &fps0,const FormalPowerSeries<MOD1> &fps1,const FormalPowerSeries<MOD2> &fps2) {assert(fps0.size() == fps1.size() && fps0.size() == fps2.size());int n = (int)fps0.size();fps.resize(n);static const mint<MOD1> im0 = mint<MOD1>(MOD0).inv();static const mint<MOD2> im1 = mint<MOD2>(MOD1).inv(), im0m1 = im1/MOD0;static const mint<MOD> m0 = MOD0, m0m1 = m0*MOD1;for (int i = 0; i < n; i++) {int y0 = fps0.a[i].x;int y1 = (im0*(fps1.a[i]-y0)).x;int y2 = (im0m1*(fps2.a[i]-y0)-im1*y1).x;fps.a[i] = m0m1*y2+y0+m0*y1;}}struct Fact {private:int N;public:vector< mint< MOD > > FACT, IFACT;Fact(int n) : N(n) {FACT.resize(n + 1);IFACT.resize(n + 1);FACT[0] = 1;for (int i = 1; i <= n; i++) {FACT[i] = FACT[i - 1] * i;}IFACT[n] = FACT[n].inv();for (int i = n-1; i >= 0; i--) {IFACT[i] = IFACT[i+1] * (i+1);}}};FPS rev() const {FPS ret(*this);reverse(ret.a.begin(), ret.a.end());return ret;}void shrink() {while (this->a.size() && this->a.back() == 0) this->a.pop_back();}static vector<FPS> subproduct_tree(const vector<mint<MOD>> &xs) {int n = (int) xs.size();int k = 1;while(k < n) k <<= 1;vector<FPS> g(2 * k, {1});for(int i = 0; i < n; i++) g[k + i] = {-xs[i], 1};for(int i = k; i-- > 1;) g[i] = g[i << 1] * g[i << 1 | 1];return g;}FPS _sqrt(int s) const {assert(this->a[0]==1);static const mint<MOD> half=mint<MOD>(1)/2;FPS f({1}),g({1}),z({1});for(int n=1;n<s;n*=2){for (int i = 0; i < n; i++) z[i]*=z[i];z.ntt(true);FPS delta(2*n),gbuf(2*n);for (int i = 0; i<n; i++) delta[n+i] = z[i] - (i<size()?this->a[i]:0) - (n+i<size()?this->a[n+i]:0);copy(g.a.begin(),g.a.end(), gbuf.a.begin());delta.ntt(false);gbuf.ntt(false);for (int i = 0;i < 2*n; i++) delta[i]*=gbuf[i];delta.ntt(true);f.resize(2*n);for(int i=n;i<2*n;i++) f[i]=-half*delta[i];if(2*n>=s)break;z=f;z.ntt(false);FPS eps=gbuf;for (int i = 0;i < 2*n;i++) eps[i]*=z[i];eps.ntt(true);for(int i = 0; i < n; i++)eps[i]=0;eps.ntt(false);for(int i = 0; i < 2*n; i++)eps[i]*=gbuf[i];eps.ntt(true);g.resize(2*n);for(int i = n; i < 2*n; i++)g[i]=-eps[i];}f.resize(s);return f;}public:vector<mint<MOD>> a;FormalPowerSeries(int sz = 0) {this->a.resize(sz, 0);}FormalPowerSeries(const std::initializer_list<mint<MOD>> v) {this->a = v;}FormalPowerSeries(const std::vector<mint<MOD>> &v) {this->a = v;}int size() const {return a.size();}void resize(size_t sz, mint<MOD> m = mint<MOD>(0)) {this->a.resize(sz,m);}FPS operator-() const { return FPS({0})-FPS(*this); }FPS operator+(const mint<MOD> &a) const { return FPS(*this) += a; }FPS operator+(const long long a) const { return FPS(*this) += a; }FPS operator+(const FPS &a) const { return FPS(*this) += a; }FPS operator-(const mint<MOD> &a) const { return FPS(*this) -= a; }FPS operator-(const long long a) const { return FPS(*this) -= a; }FPS operator-(const FPS &a) const { return FPS(*this) -= a; }FPS operator*(const mint<MOD> &a) const { return FPS(*this) *= a; }FPS operator*(const long long a) const { return FPS(*this) *= a; }FPS operator*(const FPS &a) const { return FPS(*this) *= a; }FPS operator/(const mint<MOD> &a) const { return FPS(*this) /= a;}FPS operator/(const FPS &a) const { return FPS(*this) /= a; }FPS operator%(const FPS &a) const { return FPS(*this) %= a; }FPS &operator+=(const mint<MOD> &v) {this->a[0] += v;return *this;}FPS &operator+=(const long long v) {this->a[0] += v;return *this;}FPS &operator+=(const FPS &r) {this->resize(max((int)this->size(),r.size()));for(int i = 0; i < (int)r.size(); i++) this->a[i] += r.a[i];return *this;}FPS &operator-=(const mint<MOD> &v) {this->a[0] -= v;return *this;}FPS &operator-=(const long long v) {this->a[0] -= v;return *this;}FPS &operator-=(const FPS &r) {this->resize(max((int)this->size(),r.size()));for(int i = 0; i < (int)r.size(); i++) this->a[i] -= r.a[i];return *this;}FPS &operator*=(const mint<MOD> &v) {for (int i = 0; i < this->size(); i++) this->a[i] *= v;return *this;}FPS &operator*=(const long long v) {for (int i = 0; i < this->size(); i++) this->a[i] *= v;return *this;}FPS &operator*=(const FPS &r) {this->convolution_inplace(r);return *this;}FPS &operator/=(const mint<MOD> &v){return *this *= v.inv();}FPS &operator/=(const FPS &r) {if (this->size() < r.size()) {this->a.clear();return *this;}int n = this->size() - r.size() + 1;if ((int)r.size() <= 64) {FPS f(*this), g(r);g.shrink();mint<MOD> coeff = g.a.back().inv();for (auto &x : g.a) x *= coeff;int deg = (int)f.size() - (int)g.size() + 1;int gs = g.size();FPS quo(deg);for (int i = deg - 1; i >= 0; i--) {quo[i] = f[i + gs - 1];for (int j = 0; j < gs; j++) f[i + j] -= quo[i] * g[j];}*this = quo * coeff;this->resize(n, 0);return *this;}return *this = ((*this).rev().low(n) * r.rev().inverse(n)).low(n).rev();}FPS &operator%=(const FPS &Q) {if(Q.size() > this->size()) return *this;if(Q.size() < 32) {int dQ = Q.size()-1;while(dQ && Q.a[dQ] == 0) dQ--;assert(Q.a[dQ] != 0);for(int i = this->size()-1; i >= dQ; i--){if(this->a[i] == 0) continue;mint<MOD> x = this->a[i] / Q.a[dQ];this->a[i] = 0;for(int j = 1; j <= dQ; j++){this->a[i - j] -= x * Q.a[dQ - j];}}shrink();return *this;}FPS P = (*this) / Q;P *= Q;int dR = -1;for(int i = 0; i < Q.size()-1; i++){P.a[i] = this->a[i] - P.a[i];if(P.a[i] != 0) dR = i;}this->a.resize(dR + 1);for(int i = 0; i <= dR; i++) this->a[i] = P.a[i];return *this;}FPS low(int s) const {return FPS(vector<mint<MOD>>(this->a.begin(),this->a.begin()+min(max(s,1),this->size())));}FPS inverse(int deg = -1) const {int n = this->size();assert(n != 0 && this->a[0].x != 0);if(deg == -1) deg = n;if (!any) {FPS r({this->a[0].inv()});for(int m=1;m<deg;m*=2) {FPS f(vector<mint<MOD>>(this->a.begin(), this->a.begin() + min(n, 2*m)));FPS g(r);f.resize(2*m), f.ntt(false);g.resize(2*m), g.ntt(false);for (int i = 0; i < 2*m; i++) f[i] *= g[i];f.ntt(true);f.a.erase(f.a.begin(), f.a.begin() + m);f.resize(2*m), f.ntt(false);for (int i = 0; i < 2*m; i++) f[i] *= g[i];f.ntt(true);for (int i = 0; i < 2*m; i++) f[i] = -f[i];r.a.insert(r.a.end(), f.a.begin(), f.a.begin() + m);}return r.low(deg);}else {FPS r({this->a[0].inv()});for (int i = 1; i < deg; i <<= 1)r = (r*2 - r.square()*(*this).low(i<<1)).low(i<<1);return r.low(deg);}}FPS& square_inplace() {if (this->size() == 0) {return *this;}if (!any) {int n = this->size(), sz = 1 << __lg(2*(n+n-1)-1);if (n <= 60) return *this = convolution_naive(*this,*this);this->resize(sz), this->ntt(false);for (int i = 0; i < sz; i++) this->a[i] *= this->a[i];this->ntt(true), this->resize(n+n-1);return *this;}else {int n = this->a.size();static constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617;FormalPowerSeries< mod0 > f0(n);FormalPowerSeries< mod1 > f1(n);FormalPowerSeries< mod2 > f2(n);for (int i = 0; i < n; i++) f0.a[i] = this->a[i].x, f1.a[i] = this->a[i].x, f2.a[i] = this->a[i].x;f0.square_inplace();f1.square_inplace();f2.square_inplace();crt(*this,f0,f1,f2);return *this;}}FPS square() const { return FPS(*this).square_inplace(); }FPS& differential_inplace() {const int n = (int)this->a.size();assert(n > 0);for(int i = 1; i < n; i++) this->a[i-1] = this->a[i] * i;this->a[n-1] = 0;return *this;}FPS differential() const { return FPS(*this).differential_inplace(); }FPS& integral_inplace() {const int n = (int)this->a.size();assert(n > 0);this->a.insert(this->a.begin(),0);vector<mint<MOD>> inv(n+1); inv[1] = 1;for (int i = 2; i <= n; i++) inv[i] = -inv[MOD%i]*(MOD/i);for (int i = 2; i <= n; i++) this->a[i] *= inv[i];return *this;}FPS integral() const { return FPS(*this).integ_inplace(); }FPS& log_inplace(int deg = -1) {int n = this->size();assert(n > 0 && this->a[0] == 1);if (deg == -1) deg = n;if (deg < n) this->resize(deg);FPS f_inv = this->inverse();this->differential_inplace();*this *= f_inv;this->resize(deg);this->integral_inplace();return *this;}FPS log(const int deg = -1) const { return FPS(*this).log_inplace(deg); }FPS& exp_inplace(int deg = -1) {if (!any) {int n = this->size();assert(n > 0 && (*this)[0] == 0);if (deg == -1) deg = n;assert(deg >= 0);FPS g({1}), g_fft;this->resize(deg);this->a[0] = 1;FPS h_drv = this->differential();for (int m = 1; m < deg; m *= 2) {FPS f_fft(vector<mint<MOD>>(this->a.begin(), this->a.begin() + m));f_fft.resize(2*m), f_fft.ntt(false);mint<MOD> invm = m; invm = invm.inv();if (m > 1) {FPS _f(m);for(int i = 0; i < m; i++) _f[i] = f_fft[i] * g_fft[i];_f.ntt(true);_f.a.erase(_f.a.begin(), _f.a.begin() + m/2);_f.resize(m), _f.ntt(false);for(int i = 0; i < m; i++) _f[i] *= g_fft[i];_f.ntt(true);_f.resize(m/2);for (int i = 0; i < m/2; i++) _f[i] = -_f[i];g.a.insert(g.a.end(), _f.a.begin(), _f.a.begin() + m/2);}FPS t(vector<mint<MOD>>(this->a.begin(), this->a.begin() + m));t.differential_inplace();{FPS r(vector<mint<MOD>>(h_drv.a.begin(), h_drv.a.begin() + m-1));r.resize(m); r.ntt(false);for (int i = 0; i < m; i++) r.a[i] *= f_fft.a[i];r.ntt(true);t -= r;t.a.insert(t.a.begin(), t.a.back()); t.a.pop_back();}t.resize(2*m); t.ntt(false);g_fft = g; g_fft.resize(2*m); g_fft.ntt(false);for (int i = 0; i < 2*m; i++) t.a[i] *= g_fft.a[i];t.ntt(true);t.resize(m);FPS v(vector<mint<MOD>>(this->a.begin() + m, this->a.begin() + min(deg, 2*m))); v.resize(m);t.a.insert(t.a.begin(), m-1, 0); t.a.push_back(0);t.integral_inplace();for (int i = 0; i < m; i++) v.a[i] -= t.a[m+i];v.resize(2*m); v.ntt(false);for (int i = 0; i < 2*m; i++) v.a[i] *= f_fft.a[i];v.ntt(true);v.resize(m);for (int i = 0; i < min(deg-m,m); i++) this->a[m+i] = v.a[i];}return *this;}else {assert(this->size() == 0 || this->a[0] == 0);if (deg == -1) deg = (int)this->size();FPS r({1});for (int i = 1; i < deg; i <<= 1) {r = (r*(this->low(i << 1)+mint<MOD>(1)-r.log(i << 1))).low(i << 1);}return *this = r.low(deg);}}FPS exp(const int deg = -1) const { return FPS(*this).exp_inplace(deg); }FPS& pow_inplace(ll k, int deg = -1) {int n = this->size();if (deg == -1) deg = n;assert(deg >= 0);int l = 0;while (this->a[l] == 0) ++l;if (l > deg/k) return *this = FPS(deg);mint<MOD> ic = this->a[l].inv();mint<MOD> pc = this->a[l].pow(k);this->a.erase(this->a.begin(), this->a.begin() + l);*this *= ic.x;this->log_inplace(deg-l*k);*this *= k;this->exp_inplace(deg-l*k);*this *= pc.x;this->a.insert(this->a.begin(), l*k, 0);return *this;}FPS pow(const ll k, const int deg = -1) const { return FPS(*this).pow_inplace(k, deg); }FPS pow_sparse(ll k) {assert(this->size() > 0 && this->a[0] != 0);FPS g(this->size());vector<int> fl;mint<MOD> invf0 = this->a[0].inv();vector<ll> inv(g.size(),1);g[0] = this->a[0].pow(k);for (int i = 2; i < g.size(); i++) inv[i] = MOD - (MOD / i) * inv[MOD%i] % MOD;for (int i = 0; i < this->size(); i++) {if (this->a[i] == 0) continue;fl.push_back(i);}for (int i = 1; i < g.size(); i++) {for (int j = 0; j < fl.size(); j++) {int p = fl[j];if (1 <= p && p <= i) g[i] += this->a[p]*g[i-p]*p*k;if (1 <= p && p <= i-1) g[i] -= this->a[p]*g[i-p]*(i-p);}g[i] = g[i]*this->a[0]*inv[i];}return g;}FPS& sqrt_inplace(int deg = -1) {if (deg == -1) deg = this->size();int n = this->size(), z = 0;for(;z<n&&this->a[z]==0;z++);if(z==n) {this->resize(deg); return *this;}if(z%2) return *this = {};mint<MOD> w = this->a[z].sqrt();if(w*w!=this->a[z]) return *this = {};int s=deg-z/2;mint<MOD> az = this->a[z];this->a.erase(this->a.begin(),this->a.begin()+z);*this /= az;if (!any) *this = this->_sqrt(s);else {FPS g({1});mint<MOD> two_inv = mint<MOD>(2).inv();for (int i = 1; i < s; i*=2) {g.resize(i*2);g += (*this).low(i*2)*g.inverse();g *= two_inv;}*this = g.low(s);}*this *= w;this->a.insert(this->a.begin(),z/2,0);return *this;}FPS sqrt(int deg = -1) const { return FPS(*this).sqrt_inplace(deg); }FPS& shift_inplace(const mint<MOD> &c) {int n = this->size();Fact fc(n);for (int i = 0; i < n; i++) this->a[i] *= fc.FACT[i];reverse(this->a.begin(), this->a.end());FPS g(n);mint<MOD> cp = 1;for (int i = 0; i < n; i++) g[i] = cp * fc.IFACT[i], cp *= c;this->convolution_inplace(g);this->a.resize(n);reverse(this->a.begin(), this->a.end());for (int i = 0; i < n; i++) this->a[i] *= fc.IFACT[i];return *this;}FPS shift(const mint<MOD> &c) const { return FPS(*this).shift_inplace(c); }vector<mint<MOD>> multipoint_evaluation(const vector<mint<MOD>> &xs) {auto g = subproduct_tree(xs);int m = (int) xs.size(), k = (int) g.size() / 2;g[1] = (*this) % g[1];for(int i = 2; i < k + m; i++) g[i] = g[i >> 1] % g[i];vector<mint<MOD>> ys(m);for(int i = 0; i < m; i++) {ys[i] = (g[k + i].size() == 0 ? mint<MOD>(0) : g[k + i][0]);}return ys;}vector<mint<MOD>> multipoint_evaluation(const FPS &xs) {return multipoint_evaluation(xs.a);}mint<MOD> &operator[](int x) {assert(0 <= x && x < (int)this->a.size());return a[x];}friend std::ostream &operator<<(std::ostream &os, const FPS &p) {os << "[ ";for (int i = 0; i < p.size(); ++i) {os << p.a[i] << " ";}os << "]";return os;}};template<typename T>struct Combination {private:int N;public:vector< T > FACT, IFACT;Combination(int n) : N(n) {FACT.resize(n + 1);IFACT.resize(n + 1);FACT[0] = 1;for (int i = 1; i <= n; i++) {FACT[i] = FACT[i - 1] * i;}IFACT[n] = T(1) / FACT[n];for (int i = n-1; i >= 0; i--) {IFACT[i] = IFACT[i+1] * (i+1);}}T comb(int n, int r) {if (n < 0 || r < 0 || r > n) return 0;if (r > n / 2) r = n - r;return FACT[n] * IFACT[n - r] * IFACT[r];}};int main() {int N;cin >> N;int x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;int A,B;cin >> A >> B;vector<int> a(N);for (int i = 0; i < N; i++) {cin >> a[i];}int X = abs(x1-x2), Y = abs(y1-y2);if ((X + Y) % 2 == 1|| 2*N < X+Y) {cout << 0 << endl;return 0;}FormalPowerSeries<MOD> g(N+1), h(N+1);Combination<mint<MOD>> cb(3*N);{FormalPowerSeries<MOD> g1((2*N-X-Y)/2+1),g2((2*N-X-Y)/2+1);for (int i = 0; i <= (2*N-X-Y)/2; i++) {g1[i] = cb.IFACT[X+i]*cb.IFACT[i]*(mint<MOD>(A)/(2*(A+B))).pow(X+2*i);}for (int i = 0; i <= (2*N-X-Y)/2; i++) {g2[i] = cb.IFACT[Y+i]*cb.IFACT[i]*(mint<MOD>(B)/(2*(A+B))).pow(Y+2*i);}g1*=g2;for (int i = 0; i <= (2*N-X-Y)/2; i++) {int n = (2*i+X+Y)/2;g[n] = cb.FACT[2*n] * g1[i];}}{FormalPowerSeries<MOD> h1(N+1),h2(N+1);for (int i = 0; i <= N; i++) {h1[i] = cb.IFACT[i]*cb.IFACT[i]*(mint<MOD>(A)/(2*(A+B))).pow(2*i);}for (int i = 0; i <= N; i++) {h2[i] = cb.IFACT[i]*cb.IFACT[i]*(mint<MOD>(B)/(2*(A+B))).pow(2*i);}h1*=h2;for (int i = 0; i <= N; i++) {h[i] = cb.FACT[2*i] * h1[i];}}auto f = g*h.inverse();mint<MOD> ans = 0;for (int i = 1; i <= N; i++) {ans += f[i]*a[i-1];}cout << ans << endl;return 0;}