結果
問題 | No.2383 Naphthol |
ユーザー |
|
提出日時 | 2023-06-03 18:00:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 28,598 bytes |
コンパイル時間 | 3,781 ms |
コンパイル使用メモリ | 317,800 KB |
最終ジャッジ日時 | 2025-02-13 22:25:25 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include<bits/stdc++.h>#include <immintrin.h>#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#define FOR(i,n) for(int i = 0; i < (n); i++)#define sz(c) ((int)(c).size())#define ten(x) ((int)1e##x)#define all(v) (v).begin(), (v).end()using namespace std;using ll=long long;using P = pair<ll,ll>;const long double PI=acos(-1);const ll INF=1e18;const int inf=1e9;template <typename T>bool chmin(T &a,const T& b){if (a>b){a=b;return true;}return false;}template<int MOD> struct Fp{ll val;constexpr Fp(long long v = 0) noexcept : val(v % MOD) {if (val < 0) val += MOD;}static constexpr int getmod() { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {ll a = r.val, b = MOD, u = 1, v = 0;while (b) {ll t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}constexpr bool operator < (const Fp& r) const noexcept {return this->val < r.val;}friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {Fp<MOD> res=1,r=a;while(n){if(n&1) res*=r;r*=r;n>>=1;}return res;}friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return Fp<MOD>(u);}ll get(){return val;}explicit operator bool()const{return val;}};template< uint32_t mod, bool fast = false >struct MontgomeryModInt {using mint = MontgomeryModInt;using i32 = int32_t;using i64 = int64_t;using u32 = uint32_t;using u64 = uint64_t;static constexpr u32 get_r() {u32 ret = mod;for(i32 i = 0; i < 4; i++) ret *= 2 - mod * ret;return ret;}static constexpr u32 r = get_r();static constexpr u32 n2 = -u64(mod) % mod;static_assert(r * mod == 1, "invalid, r * mod != 1");static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");u32 a;MontgomeryModInt() : a{} {}MontgomeryModInt(const i64 &x): a(reduce(u64(fast ? x : (x % mod + mod)) * n2)) {}static constexpr u32 reduce(const u64 &b) {return u32(b >> 32) + mod - u32((u64(u32(b) * r) * mod) >> 32);}constexpr mint& operator+=(const mint &p) {if(i32(a += p.a - 2 * mod) < 0) a += 2 * mod;return *this;}constexpr mint& operator-=(const mint &p) {if(i32(a -= p.a) < 0) a += 2 * mod;return *this;}constexpr mint& operator*=(const mint &p) {a = reduce(u64(a) * p.a);return *this;}constexpr mint& operator/=(const mint &p) {*this *= modinv(p);return *this;}constexpr mint operator-() const { return mint() - *this; }constexpr mint operator+(const mint &p) const { return mint(*this) += p; }constexpr mint operator-(const mint &p) const { return mint(*this) -= p; }constexpr mint operator*(const mint &p) const { return mint(*this) *= p; }constexpr mint operator/(const mint &p) const { return mint(*this) /= p; }constexpr bool operator==(const mint &p) const { return (a >= mod ? a - mod : a) == (p.a >= mod ? p.a - mod : p.a); }constexpr bool operator!=(const mint &p) const { return (a >= mod ? a - mod : a) != (p.a >= mod ? p.a - mod : p.a); }u32 get() const {u32 ret = reduce(a);return ret >= mod ? ret - mod : ret;}friend constexpr MontgomeryModInt<mod> modpow(const MontgomeryModInt<mod> &x,u64 n) noexcept {MontgomeryModInt<mod> ret(1), mul(x);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend constexpr MontgomeryModInt<mod> modinv(const MontgomeryModInt<mod> &r) noexcept {u64 a = r.get(), b = mod, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return MontgomeryModInt<mod>(u);}friend ostream &operator<<(ostream &os, const mint &p) {return os << p.get();}friend istream &operator>>(istream &is, mint &a) {i64 t;is >> t;a = mint(t);return is;}static constexpr u32 getmod() { return mod; }};template<class T,T (*op)(T,T),T (*e)()> struct SegmentTree{int n;vector<T> dat;SegmentTree(int N){n=1;while(n<N)n*=2;dat.assign(2*n,e());}void add(int k,T x){k+=n;dat[k]+=x;while(k){k>>=1;dat[k]=op(dat[k*2],dat[k*2+1]);}}void apply(int k,T x){k+=n;dat[k]=op(dat[k],x);while(k){k>>=1;dat[k]=op(dat[k*2],dat[k*2+1]);}}void set(int k,T x){k+=n;dat[k]=x;while(k){k>>=1;dat[k]=op(dat[k*2],dat[k*2+1]);}}T query(int l,int r){T prodl=e(),prodr=e();l+=n;r+=n;while(l<r){if(l&1) prodl=op(prodl,dat[l++]);if(r&1) prodr=op(dat[--r],prodr);l>>=1;r>>=1;}return op(prodl,prodr);}};template<class S,S (*op)(S,S),S (*e)(),class F,S (*mapping)(F,S),F (*composition)(F,F),F (*id)()>struct LazySegTree{private:int _n,size=1,idx=0;vector<S>seq;vector<F>lazy;void update(int k){seq[k]=op(seq[2*k],seq[2*k+1]);}void all_apply(int k,F f){seq[k]=mapping(f,seq[k]);if(k<size)lazy[k]=composition(f,lazy[k]);}void eval(int k){all_apply(2*k,lazy[k]);all_apply(2*k+1,lazy[k]);lazy[k]=id();}public:explicit LazySegTree(int n):LazySegTree(vector<S>(n,e())){}explicit LazySegTree(const vector<S>&v):_n(int(v.size())){while(size<_n)size<<=1,idx++;seq=vector<S>(2*size,e());lazy=vector<F>(2*size,id());for(int i=0;i<_n;i++)seq[size+i]=v[i];for(int i=size-1;i>=1;i--)update(i);}void set(int p,S x){p+=size;for(int i=idx;i>=1;i--)eval(p>>i);seq[p]=x;for(int i=1;i<=idx;i++)update(p>>i);}S get(int p) {assert(0 <= p && p < _n);p += size;for (int i = idx; i >= 1; i--) eval(p >> i);return seq[p];}S operator[](int p){p+=size;for(int i=idx;i>=1;i--)eval(p>>i);return seq[p];}S query(int l,int r){if(l==r)return e();S sml=e(),smr=e();l+=size,r+=size;for(int i=idx;i>=1;i--){if(((l>>i)<<i)!=l)eval(l>>i);if(((r>>i)<<i)!=r)eval(r>>i);}while(l<r){if(l&1)sml=op(sml,seq[l++]);if(r&1)smr=op(seq[--r],smr);l>>=1,r>>=1;}return op(sml,smr);}S all_query()const{return seq[1];}void apply(int p,F f){p+=size;for(int i=idx;i>=1;i--)eval(p>>i);seq[p]=mapping(f,seq[p]);for(int i=1;i<=idx;i++)update(p>>i);}void apply(int l,int r,F f){if(l==r)return ;l+=size;r+=size;for(int i=idx;i>=1;i--){if(((l>>i)<<i)!=l)eval(l>>i);if(((r>>i)<<i)!=r)eval((r-1)>>i);}int l2=l,r2=r;while(l<r){if(l&1)all_apply(l++,f);if(r&1)all_apply(--r,f);l>>=1;r>>=1;}l=l2,r=r2;for(int i=1;i<=idx;i++){if(((l>>i)<<i)!=l)update(l>>i);if(((r>>i)<<i)!=r)update((r-1)>>i);}}};ll mod(ll a,ll MOD){if(a<0) a+=MOD;return a%MOD;}ll modpow(ll a,ll n,ll mod){ll res=1;a%=mod;while (n>0){if (n & 1) res*=a;a *= a;a%=mod;n >>= 1;res%=mod;}return res;}vector<P> prime_factorize(ll N) {vector<P> res;for (ll a = 2; a * a <= N; ++a) {if (N % a != 0) continue;ll ex = 0;while(N % a == 0){++ex;N /= a;}res.push_back({a, ex});}if (N != 1) res.push_back({N, 1});return res;}ll modinv(ll a, ll mod) {ll b = mod, u = 1, v = 0;while (b) {ll t = a/b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}u %= mod;if (u < 0) u += mod;return u;}ll extGcd(ll a, ll b, ll &p, ll &q) {if (b == 0) { p = 1; q = 0; return a; }ll d = extGcd(b, a%b, q, p);q -= a/b * p;return d;}P ChineseRem(const vector<ll> &b, const vector<ll> &m) {ll r = 0, M = 1;for (int i = 0; i < (int)b.size(); ++i) {ll p, q;ll d = extGcd(M, m[i], p, q);if ((b[i] - r) % d != 0) return make_pair(0, -1);ll tmp = (b[i] - r) / d * p % (m[i]/d);r += M * tmp;M *= m[i]/d;}return make_pair(mod(r, M), M);}template< typename T >struct Combination {vector< T > _fact, _rfact, _inv;Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {_fact[0] = _rfact[sz] = _inv[0] = 1;for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;_rfact[sz] /= _fact[sz];for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];}inline T fact(int k) const { return _fact[k]; }inline T rfact(int k) const { return _rfact[k]; }inline T inv(int k) const { return _inv[k]; }T P(int n, int r) const {if(r < 0 || n < r) return 0;return fact(n) * rfact(n - r);}T C(int p, int q) const {if(q < 0 || p < q) return 0;return fact(p) * rfact(q) * rfact(p - q);}T H(int n, int r) const {if(n < 0 || r < 0) return (0);return r == 0 ? 1 : C(n + r - 1, r);}};//fast Input by yosupo#include <unistd.h>#include <algorithm>#include <array>#include <cassert>#include <cctype>#include <cstring>#include <sstream>#include <string>#include <type_traits>#include <vector>namespace fastio{/*quote from yosupo's submission in Library Checker*/int bsr(unsigned int n) {return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n);}// @param n `1 <= n`// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`int bsr(unsigned long n) {return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n);}// @param n `1 <= n`// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`int bsr(unsigned long long n) {return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n);}// @param n `1 <= n`// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`int bsr(unsigned __int128 n) {unsigned long long low = (unsigned long long)(n);unsigned long long high = (unsigned long long)(n >> 64);return high ? 127 - __builtin_clzll(high) : 63 - __builtin_ctzll(low);}namespace internal {template <class T>using is_signed_int128 =typename std::conditional<std::is_same<T, __int128_t>::value ||std::is_same<T, __int128>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int128 =typename std::conditional<std::is_same<T, __uint128_t>::value ||std::is_same<T, unsigned __int128>::value,std::true_type,std::false_type>::type;template <class T>using make_unsigned_int128 =typename std::conditional<std::is_same<T, __int128_t>::value,__uint128_t,unsigned __int128>;template <class T>using is_integral =typename std::conditional<std::is_integral<T>::value ||internal::is_signed_int128<T>::value ||internal::is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using is_signed_int = typename std::conditional<(is_integral<T>::value &&std::is_signed<T>::value) ||is_signed_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int =typename std::conditional<(is_integral<T>::value &&std::is_unsigned<T>::value) ||is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using to_unsigned = typename std::conditional<is_signed_int128<T>::value,make_unsigned_int128<T>,typename std::conditional<std::is_signed<T>::value,std::make_unsigned<T>,std::common_type<T>>::type>::type;template <class T>using is_integral_t = std::enable_if_t<is_integral<T>::value>;template <class T>using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;template <class T>using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;template <class T> using to_unsigned_t = typename to_unsigned<T>::type;} // namespace internalstruct Scanner {public:Scanner(const Scanner&) = delete;Scanner& operator=(const Scanner&) = delete;Scanner(FILE* fp) : fd(fileno(fp)) {}void read() {}template <class H, class... T> void read(H& h, T&... t) {bool f = read_single(h);assert(f);read(t...);}int read_unsafe() { return 0; }template <class H, class... T> int read_unsafe(H& h, T&... t) {bool f = read_single(h);if (!f) return 0;return 1 + read_unsafe(t...);}int close() { return ::close(fd); }private:static constexpr int SIZE = 1 << 15;int fd = -1;std::array<char, SIZE + 1> line;int st = 0, ed = 0;bool eof = false;bool read_single(std::string& ref) {if (!skip_space()) return false;ref = "";while (true) {char c = top();if (c <= ' ') break;ref += c;st++;}return true;}bool read_single(double& ref) {std::string s;if (!read_single(s)) return false;ref = std::stod(s);return true;}template <class T,std::enable_if_t<std::is_same<T, char>::value>* = nullptr>bool read_single(T& ref) {if (!skip_space<50>()) return false;ref = top();st++;return true;}template <class T,internal::is_signed_int_t<T>* = nullptr,std::enable_if_t<!std::is_same<T, char>::value>* = nullptr>bool read_single(T& sref) {using U = internal::to_unsigned_t<T>;if (!skip_space<50>()) return false;bool neg = false;if (line[st] == '-') {neg = true;st++;}U ref = 0;do {ref = 10 * ref + (line[st++] & 0x0f);} while (line[st] >= '0');sref = neg ? -ref : ref;return true;}template <class U,internal::is_unsigned_int_t<U>* = nullptr,std::enable_if_t<!std::is_same<U, char>::value>* = nullptr>bool read_single(U& ref) {if (!skip_space<50>()) return false;ref = 0;do {ref = 10 * ref + (line[st++] & 0x0f);} while (line[st] >= '0');return true;}bool reread() {if (ed - st >= 50) return true;if (st > SIZE / 2) {std::memmove(line.data(), line.data() + st, ed - st);ed -= st;st = 0;}if (eof) return false;auto u = ::read(fd, line.data() + ed, SIZE - ed);if (u == 0) {eof = true;line[ed] = '\0';u = 1;}ed += int(u);line[ed] = char(127);return true;}char top() {if (st == ed) {bool f = reread();assert(f);}return line[st];}template <int TOKEN_LEN = 0>bool skip_space() {while (true) {while (line[st] <= ' ') st++;if (ed - st > TOKEN_LEN) return true;if (st > ed) st = ed;for (auto i = st; i < ed; i++) {if (line[i] <= ' ') return true;}if (!reread()) return false;}}};//fast Output by ei1333/*** @brief Printer(高速出力)*/struct Printer {public:explicit Printer(FILE *fp) : fp(fp) {}~Printer() { flush(); }template< bool f = false, typename T, typename... E >void write(const T &t, const E &... e) {if(f) write_single(' ');write_single(t);write< true >(e...);}template< typename... T >void writeln(const T &...t) {write(t...);write_single('\n');}void flush() {fwrite(line, 1, st - line, fp);st = line;}private:FILE *fp = nullptr;static constexpr size_t line_size = 1 << 16;static constexpr size_t int_digits = 20;char line[line_size + 1] = {};char small[32] = {};char *st = line;template< bool f = false >void write() {}void write_single(const char &t) {if(st + 1 >= line + line_size) flush();*st++ = t;}template< typename T, enable_if_t< is_integral< T >::value, int > = 0 >void write_single(T s) {if(st + int_digits >= line + line_size) flush();if(s == 0) {write_single('0');return;}if(s < 0) {write_single('-');s = -s;}char *mp = small + sizeof(small);typename make_unsigned< T >::type y = s;size_t len = 0;while(y > 0) {*--mp = y % 10 + '0';y /= 10;++len;}memmove(st, mp, len);st += len;}void write_single(const string &s) {for(auto &c : s) write_single(c);}void write_single(const char *s) {while(*s != 0) write_single(*s++);}template< typename T >void write_single(const vector< T > &s) {for(size_t i = 0; i < s.size(); i++) {if(i) write_single(' ');write_single(s[i]);}}};}; //namespace fastiousing u64=unsigned long long;u64 RNG_64() {static uint64_t x_= uint64_t(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count())* 10150724397891781847ULL;x_ ^= x_ << 7;return x_ ^= x_ >> 9;}u64 RNG(u64 lim) { return RNG_64() % lim; }ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }struct modint61 {static constexpr bool is_modint = true;static constexpr ll mod = (1LL << 61) - 1;ll val;constexpr modint61(const ll x = 0) : val(x) {while (val < 0) val += mod;while (val >= mod) val -= mod;}bool operator<(const modint61 &other) const {return val < other.val;} // To use std::mapbool operator==(const modint61 &p) const { return val == p.val; }bool operator!=(const modint61 &p) const { return val != p.val; }modint61 &operator+=(const modint61 &p) {if ((val += p.val) >= mod) val -= mod;return *this;}modint61 &operator-=(const modint61 &p) {if ((val += mod - p.val) >= mod) val -= mod;return *this;}modint61 &operator*=(const modint61 &p) {ll a = val, b = p.val;const ll MASK30 = (1LL << 30) - 1;const ll MASK31 = (1LL << 31) - 1;const ll MASK61 = (1LL << 61) - 1;ll au = a >> 31, ad = a & MASK31;ll bu = b >> 31, bd = b & MASK31;ll x = ad * bu + au * bd;ll xu = x >> 30, xd = x & MASK30;x = au * bu * 2 + xu + (xd << 31) + ad * bd;xu = x >> 61, xd = x & MASK61;x = xu + xd;if (x >= MASK61) x -= MASK61;val = x;return *this;}modint61 operator-() const { return modint61(get_mod() - val); }modint61 &operator/=(const modint61 &p) {*this *= p.inverse();return *this;}modint61 operator+(const modint61 &p) const { return modint61(*this) += p; }modint61 operator-(const modint61 &p) const { return modint61(*this) -= p; }modint61 operator*(const modint61 &p) const { return modint61(*this) *= p; }modint61 operator/(const modint61 &p) const { return modint61(*this) /= p; }modint61 inverse() const {ll a = val, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;swap(a -= t * b, b), swap(u -= t * v, v);}return modint61(u);}modint61 pow(int64_t n) const {modint61 ret(1), mul(val);while (n > 0) {if (n & 1) ret = ret * mul;mul = mul * mul;n >>= 1;}return ret;}static constexpr ll get_mod() { return mod; }#ifdef FASTIOvoid write() { fastio::printer.write(val); }void read() { fastio::scanner.read(val); }#endif};struct RollingHash {using mint = modint61;static constexpr u64 mod = mint::get_mod();const mint base;vector<mint> power;static inline mint generate_base() { return RNG(mod); }inline void expand(size_t sz) {if (power.size() < sz + 1) {int pre_sz = (int)power.size();power.resize(sz + 1);for(int i=pre_sz - 1;i<sz;i++) power[i + 1] = power[i] * base;}}explicit RollingHash(mint base = generate_base()) : base(base), power{1} {}template <typename STRING>vector<mint> build(const STRING& s) const {int sz = s.size();vector<mint> hashed(sz + 1);for (int i = 0; i < sz; i++) { hashed[i + 1] = hashed[i] * base + s[i]; }return hashed;}mint query(const vector<mint>& s, int l, int r) {expand(r - l);return (s[r] - s[l] * power[r - l]).val;}mint combine(mint h1, mint h2, int h2len) {expand(h2len);return h1 * power[h2len] + h2;}mint add_char(mint h, int x) { return h * base + mint(x); }int lcp(const vector<mint>& a, int l1, int r1, const vector<mint>& b, int l2,int r2) {int len = min(r1 - l1, r2 - l2);int low = 0, high = len + 1;while (high - low > 1) {int mid = (low + high) / 2;if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid))low = mid;elsehigh = mid;}return low;}};inline constexpr int msb(u64 x) {int res = x ? 0 : -1;if (x & 0xFFFFFFFF00000000) x &= 0xFFFFFFFF00000000, res += 32;if (x & 0xFFFF0000FFFF0000) x &= 0xFFFF0000FFFF0000, res += 16;if (x & 0xFF00FF00FF00FF00) x &= 0xFF00FF00FF00FF00, res += 8;if (x & 0xF0F0F0F0F0F0F0F0) x &= 0xF0F0F0F0F0F0F0F0, res += 4;if (x & 0xCCCCCCCCCCCCCCCC) x &= 0xCCCCCCCCCCCCCCCC, res += 2;return res + ((x & 0xAAAAAAAAAAAAAAAA) ? 1 : 0);}inline constexpr int ceil_log2(u64 x) { return x ? msb(x - 1) + 1 : 0; }template<class T> class infinity {public:static constexpr T value = std::numeric_limits<T>::max() / 2;static constexpr T mvalue = std::numeric_limits<T>::min() / 2;static constexpr T max = std::numeric_limits<T>::max();static constexpr T min = std::numeric_limits<T>::min();};#if __cplusplus <= 201402Ltemplate<class T> constexpr T infinity<T>::value;template<class T> constexpr T infinity<T>::mvalue;template<class T> constexpr T infinity<T>::max;template<class T> constexpr T infinity<T>::min;#endiftemplate<class T = ll, bool is_max = false> class LiChaoTree {private:struct Line {T a, b;int idx;T get(T x) const { return a * x + b; }Line() = default;Line(T a, T b, int id) : a(a), b(b), idx(id) {}};int line_count = 0;int ori, n;std::vector<T> xs;std::vector<Line> lns;void add_line(int k, int a, int b, const Line& line) {if (a + 1 == b) {if (line.get(xs[a]) < lns[k].get(xs[a])) lns[k] = line;return;}int m = (a + b) >> 1;T x1 = lns[k].get(xs[a]), x2 = line.get(xs[a]);T y1 = lns[k].get(xs[b - 1]), y2 = line.get(xs[b - 1]);if (x1 <= x2 && y1 <= y2) return;if (x2 <= x1 && y2 <= y1) {lns[k] = line;return;}if (lns[k].get(xs[m]) <= line.get(xs[m])) {if (y1 < y2) add_line(k << 1, a, m, line);else add_line(k << 1 | 1, m, b, line);}else {if (y1 < y2) add_line(k << 1 | 1, m, b, lns[k]);else add_line(k << 1, a, m, lns[k]);lns[k] = line;}}void add_segment(int k, int a, int b, int l, int r, const Line& line) {if (l <= a && b <= r) {add_line(k, a, b, line);return;}if (r <= a || b <= l) return;int m = (a + b) >> 1;add_segment(k << 1, a, m, l, r, line);add_segment(k << 1 | 1, m, b, l, r, line);}public:LiChaoTree() : LiChaoTree({0}) {}LiChaoTree(const std::vector<T>& xs_) { init(xs_); }void init(const std::vector<T>& xs_) {xs = xs_.empty() ? std::vector<T>{0} : xs_;ori = xs.size();n = 1 << ceil_log2(ori);xs.reserve(n);for(int i=xs_.size();i<n;i++) xs.push_back(xs_[i] + 1);lns.assign(n << 1,Line{0, is_max ? infinity<T>::min : infinity<T>::max, -1});}int add_segment(int l, int r, T x, T y) {assert(0 <= l && l <= r && r <= ori);add_segment(1, 0, n, l, r,Line{is_max ? -x : x, is_max ? -y : y, line_count});return line_count++;}int add_line(T x, T y) {add_line(1, 0, n, Line{is_max ? -x : x, is_max ? -y : y, line_count});return line_count++;}T get_min(int k) const {int x = k + n;T res = lns[x].get(xs[k]);while (x >>= 1) {const T y = lns[x].get(xs[k]);if(is_max) chmin(res, -y );else chmin(res, y);}return res;}struct line {T a, b;int idx;};line get_min_line(int k) const {int x = k + n;T mn = lns[x].get(xs[k]);Line res = lns[x];while (x >>= 1) {const T y = lns[x].get(xs[k]);if (chmin(mn, is_max ? -y : y)) res = lns[x];}return line{is_max ? -res.a : res.a, is_max ? -res.b : res.b, res.idx};}};using mint=MontgomeryModInt<998244353>;int main(){fastio::Scanner sc(stdin);fastio::Printer pr(stdout);#define in(...) sc.read(__VA_ARGS__)#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)#define out(...) pr.write(__VA_ARGS__)#define outln(...) pr.writeln(__VA_ARGS__)#define outspace(...) pr.write(__VA_ARGS__),pr.write(' ')#define rall(v) (v).rbegin(), (v).rend()#define fi first#define se second/**/INT(n,k);assert(1<=n&&n<=100000&&1<=k&&k<=n*2+4);Combination<mint> C(200200);if(n==1){mint ans=0;for(int i=0;i<6;i++){if(k%(6/gcd(6,i))==0) ans+=C.C(gcd(6,i),k/(6/gcd(6,i)));}ans*=C.inv(12);ans+=C.C(3-k%2*(1-6%2),k/2)*C.inv(2);outln(ans.get());return 0;}mint ans=C.C(n*2+4,k);if(n%2==1&&k%2==1) ans+=C.C(n+1,(k-1)/2)*2;else if(n%2==1&&k%2==0) ans+=C.C(n+1,k/2)+C.C(n+1,(k-2)/2);else if(n%2==0&&k%2==0) ans+=C.C(n+2,k/2);if(k%2==0) ans+=C.C(n+2,k/2)*2;ans*=C.inv(4);outln(ans.get());}