結果
| 問題 |
No.2801 Unique Maximum
|
| コンテスト | |
| ユーザー |
 kaichou243
|
| 提出日時 | 2025-02-23 02:43:11 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 65,139 bytes |
| コンパイル時間 | 8,054 ms |
| コンパイル使用メモリ | 398,072 KB |
| 実行使用メモリ | 23,236 KB |
| 最終ジャッジ日時 | 2025-02-23 02:43:30 |
| 合計ジャッジ時間 | 18,587 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 TLE * 1 |
| other | AC * 4 TLE * 1 -- * 16 |
ソースコード
#include<bits/stdc++.h>
#include <immintrin.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#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< 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; }
};
ll mod(ll a, ll mod) {
return (a%mod+mod)%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);
}
namespace NTT {
using i64 = int64_t;
__attribute__((target("sse4.2"))) inline __m128i my128_mullo_epu32(
const __m128i &a, const __m128i &b) {
return _mm_mullo_epi32(a, b);
}
__attribute__((target("sse4.2"))) inline __m128i my128_mulhi_epu32(
const __m128i &a, const __m128i &b) {
__m128i a13 = _mm_shuffle_epi32(a, 0xF5);
__m128i b13 = _mm_shuffle_epi32(b, 0xF5);
__m128i prod02 = _mm_mul_epu32(a, b);
__m128i prod13 = _mm_mul_epu32(a13, b13);
__m128i prod = _mm_unpackhi_epi64(_mm_unpacklo_epi32(prod02, prod13),
_mm_unpackhi_epi32(prod02, prod13));
return prod;
}
__attribute__((target("sse4.2"))) inline __m128i montgomery_mul_128(
const __m128i &a, const __m128i &b, const __m128i &r, const __m128i &m1) {
return _mm_sub_epi32(
_mm_add_epi32(my128_mulhi_epu32(a, b), m1),
my128_mulhi_epu32(my128_mullo_epu32(my128_mullo_epu32(a, b), r), m1));
}
__attribute__((target("sse4.2"))) inline __m128i montgomery_add_128(
const __m128i &a, const __m128i &b, const __m128i &m2, const __m128i &m0) {
__m128i ret = _mm_sub_epi32(_mm_add_epi32(a, b), m2);
return _mm_add_epi32(_mm_and_si128(_mm_cmpgt_epi32(m0, ret), m2), ret);
}
__attribute__((target("sse4.2"))) inline __m128i montgomery_sub_128(
const __m128i &a, const __m128i &b, const __m128i &m2, const __m128i &m0) {
__m128i ret = _mm_sub_epi32(a, b);
return _mm_add_epi32(_mm_and_si128(_mm_cmpgt_epi32(m0, ret), m2), ret);
}
__attribute__((target("avx2"))) inline __m256i my256_mullo_epu32(
const __m256i &a, const __m256i &b) {
return _mm256_mullo_epi32(a, b);
}
__attribute__((target("avx2"))) inline __m256i my256_mulhi_epu32(
const __m256i &a, const __m256i &b) {
__m256i a13 = _mm256_shuffle_epi32(a, 0xF5);
__m256i b13 = _mm256_shuffle_epi32(b, 0xF5);
__m256i prod02 = _mm256_mul_epu32(a, b);
__m256i prod13 = _mm256_mul_epu32(a13, b13);
__m256i prod = _mm256_unpackhi_epi64(_mm256_unpacklo_epi32(prod02, prod13),
_mm256_unpackhi_epi32(prod02, prod13));
return prod;
}
__attribute__((target("avx2"))) inline __m256i montgomery_mul_256(
const __m256i &a, const __m256i &b, const __m256i &r, const __m256i &m1) {
return _mm256_sub_epi32(
_mm256_add_epi32(my256_mulhi_epu32(a, b), m1),
my256_mulhi_epu32(my256_mullo_epu32(my256_mullo_epu32(a, b), r), m1));
}
__attribute__((target("avx2"))) inline __m256i montgomery_add_256(
const __m256i &a, const __m256i &b, const __m256i &m2, const __m256i &m0) {
__m256i ret = _mm256_sub_epi32(_mm256_add_epi32(a, b), m2);
return _mm256_add_epi32(_mm256_and_si256(_mm256_cmpgt_epi32(m0, ret), m2),
ret);
}
__attribute__((target("avx2"))) inline __m256i montgomery_sub_256(
const __m256i &a, const __m256i &b, const __m256i &m2, const __m256i &m0) {
__m256i ret = _mm256_sub_epi32(a, b);
return _mm256_add_epi32(_mm256_and_si256(_mm256_cmpgt_epi32(m0, ret), m2),
ret);
}
int calc_primitive_root(int mod) {
if (mod == 2) return 1;
if (mod == 167772161) return 3;
if (mod == 469762049) return 3;
if (mod == 754974721) return 11;
if (mod == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
long long x = (mod - 1) / 2;
while (x % 2 == 0) x /= 2;
for (long long i = 3; i * i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) x /= i;
}
}
if (x > 1) divs[cnt++] = x;
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (modpow(g, (mod - 1) / divs[i], mod) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
int get_fft_size(int N, int M) {
int size_a = 1, size_b = 1;
while (size_a < N) size_a <<= 1;
while (size_b < M) size_b <<= 1;
return max(size_a, size_b) << 1;
}
constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
template <class mint>
struct fft_info{
static constexpr int rank2 = bsf_constexpr(mint::getmod() - 1);
std::array<mint, rank2 + 1> root; // root[i]^(2^i) == 1
std::array<mint, rank2 + 1> iroot; // root[i] * iroot[i] == 1
std::array<mint, std::max(0, rank2 - 2 + 1)> rate2;
std::array<mint, std::max(0, rank2 - 2 + 1)> irate2;
std::array<mint, std::max(0, rank2 - 3 + 1)> rate3;
std::array<mint, std::max(0, rank2 - 3 + 1)> irate3;
int g;
fft_info(){
int MOD=mint::getmod();
g=calc_primitive_root(MOD);
root[rank2] = modpow(mint(g),(MOD - 1) >> rank2);
iroot[rank2] = modinv(root[rank2]);
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
}
};
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// number-theoretic transform
template <class mint>
void trans(std::vector<mint>& a) {
int n = int(a.size());
int h = ceil_pow2(n);
int MOD=a[0].getmod();
static const fft_info<mint> info;
int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
mint rot = 1;
for (int s = 0; s < (1 << len); s++) {
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
if (s + 1 != (1 << len))
rot *= info.rate2[bsf(~(unsigned int)(s))];
}
len++;
} else {
// 4-base
int p = 1 << (h - len - 2);
mint rot = 1, imag = info.root[2];
for (int s = 0; s < (1 << len); s++) {
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto mod2 = 1ULL * MOD * MOD;
auto a0 = 1ULL * a[i + offset].get();
auto a1 = 1ULL * a[i + offset + p].get() * rot.get();
auto a2 = 1ULL * a[i + offset + 2 * p].get() * rot2.get();
auto a3 = 1ULL * a[i + offset + 3 * p].get() * rot3.get();
auto a1na3imag =
1ULL * mint(a1 + mod2 - a3).get() * imag.get();
auto na2 = mod2 - a2;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
}
if (s + 1 != (1 << len))
rot *= info.rate3[bsf(~(unsigned int)(s))];
}
len += 2;
}
}
}
template <class mint>
void trans_inv(std::vector<mint>& a) {
int n = int(a.size());
int h = ceil_pow2(n);
static const fft_info<mint> info;
int MOD=a[0].getmod();
int len = h; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len) {
if (len == 1) {
int p = 1 << (h - len);
mint irot = 1;
for (int s = 0; s < (1 << (len - 1)); s++) {
int offset = s << (h - len + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)(MOD + l.get() - r.get()) *
irot.get();
;
}
if (s + 1 != (1 << (len - 1)))
irot *= info.irate2[bsf(~(unsigned int)(s))];
}
len--;
} else {
// 4-base
int p = 1 << (h - len);
mint irot = 1, iimag = info.iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
auto a0 = 1ULL * a[i + offset + 0 * p].get();
auto a1 = 1ULL * a[i + offset + 1 * p].get();
auto a2 = 1ULL * a[i + offset + 2 * p].get();
auto a3 = 1ULL * a[i + offset + 3 * p].get();
auto a2na3iimag =
1ULL *
mint((MOD + a2 - a3) * iimag.get()).get();
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + 1 * p] =
(a0 + (MOD - a1) + a2na3iimag) * irot.get();
a[i + offset + 2 * p] =
(a0 + a1 + (MOD - a2) + (MOD - a3)) *
irot2.get();
a[i + offset + 3 * p] =
(a0 + (MOD - a1) + (MOD - a2na3iimag)) *
irot3.get();
}
if (s + 1 != (1 << (len - 2)))
irot *= info.irate3[bsf(~(unsigned int)(s))];
}
len -= 2;
}
}
}
namespace ntt_inner {
using u64 = uint64_t;
constexpr uint32_t get_pr(uint32_t mod) {
if (mod == 2) return 1;
u64 ds[32] = {};
int idx = 0;
u64 m = mod - 1;
for (u64 i = 2; i * i <= m; ++i) {
if (m % i == 0) {
ds[idx++] = i;
while (m % i == 0) m /= i;
}
}
if (m != 1) ds[idx++] = m;
uint32_t pr = 2;
while (1) {
int flg = 1;
for (int i = 0; i < idx; ++i) {
u64 a = pr, b = (mod - 1) / ds[i], r = 1;
while (b) {
if (b & 1) r = r * a % mod;
a = a * a % mod;
b >>= 1;
}
if (r == 1) {
flg = 0;
break;
}
}
if (flg == 1) break;
++pr;
}
return pr;
}
constexpr int SZ_FFT_BUF = 1 << 23;
uint32_t _buf1[SZ_FFT_BUF] __attribute__((aligned(64)));
uint32_t _buf2[SZ_FFT_BUF] __attribute__((aligned(64)));
} // namespace ntt_inner
template <typename mint>
struct NumberTheoreticTransform {
static constexpr uint32_t mod = mint::getmod();
static constexpr uint32_t pr = ntt_inner::get_pr(mint::getmod());
static constexpr int level = __builtin_ctzll(mod - 1);
mint dw[level], dy[level];
mint *buf1, *buf2;
constexpr NumberTheoreticTransform() {
setwy(level);
union raw_cast {
mint dat;
uint32_t _;
};
buf1 = &(((raw_cast *)(ntt_inner::_buf1))->dat);
buf2 = &(((raw_cast *)(ntt_inner::_buf2))->dat);
}
constexpr void setwy(int k) {
mint w[level], y[level];
w[k - 1] = modpow(mint(pr),(mod - 1) / (1 << k));
y[k - 1] = modinv(w[k - 1]);
for (int i = k - 2; i > 0; --i)
w[i] = w[i + 1] * w[i + 1], y[i] = y[i + 1] * y[i + 1];
dw[0] = dy[0] = w[1] * w[1];
dw[1] = w[1], dy[1] = y[1], dw[2] = w[2], dy[2] = y[2];
for (int i = 3; i < k; ++i) {
dw[i] = dw[i - 1] * y[i - 2] * w[i];
dy[i] = dy[i - 1] * w[i - 2] * y[i];
}
}
__attribute__((target("avx2"))) void ntt(mint *a, int n) {
int k = n ? __builtin_ctz(n) : 0;
if (k == 0) return;
if (k == 1) {
mint a1 = a[1];
a[1] = a[0] - a[1];
a[0] = a[0] + a1;
return;
}
if (k & 1) {
int v = 1 << (k - 1);
if (v < 8) {
for (int j = 0; j < v; ++j) {
mint ajv = a[j + v];
a[j + v] = a[j] - ajv;
a[j] += ajv;
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
int j0 = 0;
int j1 = v;
for (; j0 < v; j0 += 8, j1 += 8) {
__m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
__m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
__m256i naj = montgomery_add_256(T0, T1, m2, m0);
__m256i najv = montgomery_sub_256(T0, T1, m2, m0);
_mm256_storeu_si256((__m256i *)(a + j0), naj);
_mm256_storeu_si256((__m256i *)(a + j1), najv);
}
}
}
int u = 1 << (2 + (k & 1));
int v = 1 << (k - 2 - (k & 1));
mint one = mint(1);
mint imag = dw[1];
while (v) {
if (v == 1) {
mint ww = one, xx = one, wx = one;
for (int jh = 0; jh < u;) {
ww = xx * xx, wx = ww * xx;
mint t0 = a[jh + 0], t1 = a[jh + 1] * xx;
mint t2 = a[jh + 2] * ww, t3 = a[jh + 3] * wx;
mint t0p2 = t0 + t2, t1p3 = t1 + t3;
mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag;
a[jh + 0] = t0p2 + t1p3, a[jh + 1] = t0p2 - t1p3;
a[jh + 2] = t0m2 + t1m3, a[jh + 3] = t0m2 - t1m3;
xx *= dw[__builtin_ctz((jh += 4))];
}
} else if (v == 4) {
const __m128i m0 = _mm_set1_epi32(0);
const __m128i m1 = _mm_set1_epi32(mod);
const __m128i m2 = _mm_set1_epi32(mod + mod);
const __m128i r = _mm_set1_epi32(mint::r);
const __m128i Imag = _mm_set1_epi32(imag.a);
mint ww = one, xx = one, wx = one;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = v;
for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i T0P2 = montgomery_add_128(T0, T2, m2, m0);
const __m128i T1P3 = montgomery_add_128(T1, T3, m2, m0);
const __m128i T0M2 = montgomery_sub_128(T0, T2, m2, m0);
const __m128i T1M3 = montgomery_mul_128(
montgomery_sub_128(T1, T3, m2, m0), Imag, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_sub_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j2),
montgomery_add_128(T0M2, T1M3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j3),
montgomery_sub_128(T0M2, T1M3, m2, m0));
}
} else {
ww = xx * xx, wx = ww * xx;
const __m128i WW = _mm_set1_epi32(ww.a);
const __m128i WX = _mm_set1_epi32(wx.a);
const __m128i XX = _mm_set1_epi32(xx.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i MT1 = montgomery_mul_128(T1, XX, r, m1);
const __m128i MT2 = montgomery_mul_128(T2, WW, r, m1);
const __m128i MT3 = montgomery_mul_128(T3, WX, r, m1);
const __m128i T0P2 = montgomery_add_128(T0, MT2, m2, m0);
const __m128i T1P3 = montgomery_add_128(MT1, MT3, m2, m0);
const __m128i T0M2 = montgomery_sub_128(T0, MT2, m2, m0);
const __m128i T1M3 = montgomery_mul_128(
montgomery_sub_128(MT1, MT3, m2, m0), Imag, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_sub_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j2),
montgomery_add_128(T0M2, T1M3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j3),
montgomery_sub_128(T0M2, T1M3, m2, m0));
}
}
xx *= dw[__builtin_ctz((jh += 4))];
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m1 = _mm256_set1_epi32(mod);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
const __m256i r = _mm256_set1_epi32(mint::r);
const __m256i Imag = _mm256_set1_epi32(imag.a);
mint ww = one, xx = one, wx = one;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = v;
for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i T0P2 = montgomery_add_256(T0, T2, m2, m0);
const __m256i T1P3 = montgomery_add_256(T1, T3, m2, m0);
const __m256i T0M2 = montgomery_sub_256(T0, T2, m2, m0);
const __m256i T1M3 = montgomery_mul_256(
montgomery_sub_256(T1, T3, m2, m0), Imag, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_sub_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j2),
montgomery_add_256(T0M2, T1M3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j3),
montgomery_sub_256(T0M2, T1M3, m2, m0));
}
} else {
ww = xx * xx, wx = ww * xx;
const __m256i WW = _mm256_set1_epi32(ww.a);
const __m256i WX = _mm256_set1_epi32(wx.a);
const __m256i XX = _mm256_set1_epi32(xx.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i MT1 = montgomery_mul_256(T1, XX, r, m1);
const __m256i MT2 = montgomery_mul_256(T2, WW, r, m1);
const __m256i MT3 = montgomery_mul_256(T3, WX, r, m1);
const __m256i T0P2 = montgomery_add_256(T0, MT2, m2, m0);
const __m256i T1P3 = montgomery_add_256(MT1, MT3, m2, m0);
const __m256i T0M2 = montgomery_sub_256(T0, MT2, m2, m0);
const __m256i T1M3 = montgomery_mul_256(
montgomery_sub_256(MT1, MT3, m2, m0), Imag, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_sub_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j2),
montgomery_add_256(T0M2, T1M3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j3),
montgomery_sub_256(T0M2, T1M3, m2, m0));
}
}
xx *= dw[__builtin_ctz((jh += 4))];
}
}
u <<= 2;
v >>= 2;
}
}
__attribute__((target("avx2"))) void intt(mint *a, int n,
int normalize = true) {
int k = n ? __builtin_ctz(n) : 0;
if (k == 0) return;
if (k == 1) {
mint a1 = a[1];
a[1] = a[0] - a[1];
a[0] = a[0] + a1;
if (normalize) {
a[0] *= modinv(mint(2));
a[1] *= modinv(mint(2));
}
return;
}
int u = 1 << (k - 2);
int v = 1;
mint one = mint(1);
mint imag = dy[1];
while (u) {
if (v == 1) {
mint ww = one, xx = one, yy = one;
u <<= 2;
for (int jh = 0; jh < u;) {
ww = xx * xx, yy = xx * imag;
mint t0 = a[jh + 0], t1 = a[jh + 1];
mint t2 = a[jh + 2], t3 = a[jh + 3];
mint t0p1 = t0 + t1, t2p3 = t2 + t3;
mint t0m1 = (t0 - t1) * xx, t2m3 = (t2 - t3) * yy;
a[jh + 0] = t0p1 + t2p3, a[jh + 2] = (t0p1 - t2p3) * ww;
a[jh + 1] = t0m1 + t2m3, a[jh + 3] = (t0m1 - t2m3) * ww;
xx *= dy[__builtin_ctz(jh += 4)];
}
} else if (v == 4) {
const __m128i m0 = _mm_set1_epi32(0);
const __m128i m1 = _mm_set1_epi32(mod);
const __m128i m2 = _mm_set1_epi32(mod + mod);
const __m128i r = _mm_set1_epi32(mint::r);
const __m128i Imag = _mm_set1_epi32(imag.a);
mint ww = one, xx = one, yy = one;
u <<= 2;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = v + v;
int j3 = j2 + v;
for (; j0 < v; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i T0P1 = montgomery_add_128(T0, T1, m2, m0);
const __m128i T2P3 = montgomery_add_128(T2, T3, m2, m0);
const __m128i T0M1 = montgomery_sub_128(T0, T1, m2, m0);
const __m128i T2M3 = montgomery_mul_128(
montgomery_sub_128(T2, T3, m2, m0), Imag, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P1, T2P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j2),
montgomery_sub_128(T0P1, T2P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_add_128(T0M1, T2M3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j3),
montgomery_sub_128(T0M1, T2M3, m2, m0));
}
} else {
ww = xx * xx, yy = xx * imag;
const __m128i WW = _mm_set1_epi32(ww.a);
const __m128i XX = _mm_set1_epi32(xx.a);
const __m128i YY = _mm_set1_epi32(yy.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i T0P1 = montgomery_add_128(T0, T1, m2, m0);
const __m128i T2P3 = montgomery_add_128(T2, T3, m2, m0);
const __m128i T0M1 = montgomery_mul_128(
montgomery_sub_128(T0, T1, m2, m0), XX, r, m1);
__m128i T2M3 = montgomery_mul_128(
montgomery_sub_128(T2, T3, m2, m0), YY, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P1, T2P3, m2, m0));
_mm_storeu_si128(
(__m128i *)(a + j2),
montgomery_mul_128(montgomery_sub_128(T0P1, T2P3, m2, m0), WW,
r, m1));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_add_128(T0M1, T2M3, m2, m0));
_mm_storeu_si128(
(__m128i *)(a + j3),
montgomery_mul_128(montgomery_sub_128(T0M1, T2M3, m2, m0), WW,
r, m1));
}
}
xx *= dy[__builtin_ctz(jh += 4)];
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m1 = _mm256_set1_epi32(mod);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
const __m256i r = _mm256_set1_epi32(mint::r);
const __m256i Imag = _mm256_set1_epi32(imag.a);
mint ww = one, xx = one, yy = one;
u <<= 2;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = v + v;
int j3 = j2 + v;
for (; j0 < v; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i T0P1 = montgomery_add_256(T0, T1, m2, m0);
const __m256i T2P3 = montgomery_add_256(T2, T3, m2, m0);
const __m256i T0M1 = montgomery_sub_256(T0, T1, m2, m0);
const __m256i T2M3 = montgomery_mul_256(
montgomery_sub_256(T2, T3, m2, m0), Imag, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P1, T2P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j2),
montgomery_sub_256(T0P1, T2P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_add_256(T0M1, T2M3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j3),
montgomery_sub_256(T0M1, T2M3, m2, m0));
}
} else {
ww = xx * xx, yy = xx * imag;
const __m256i WW = _mm256_set1_epi32(ww.a);
const __m256i XX = _mm256_set1_epi32(xx.a);
const __m256i YY = _mm256_set1_epi32(yy.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i T0P1 = montgomery_add_256(T0, T1, m2, m0);
const __m256i T2P3 = montgomery_add_256(T2, T3, m2, m0);
const __m256i T0M1 = montgomery_mul_256(
montgomery_sub_256(T0, T1, m2, m0), XX, r, m1);
const __m256i T2M3 = montgomery_mul_256(
montgomery_sub_256(T2, T3, m2, m0), YY, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P1, T2P3, m2, m0));
_mm256_storeu_si256(
(__m256i *)(a + j2),
montgomery_mul_256(montgomery_sub_256(T0P1, T2P3, m2, m0), WW,
r, m1));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_add_256(T0M1, T2M3, m2, m0));
_mm256_storeu_si256(
(__m256i *)(a + j3),
montgomery_mul_256(montgomery_sub_256(T0M1, T2M3, m2, m0), WW,
r, m1));
}
}
xx *= dy[__builtin_ctz(jh += 4)];
}
}
u >>= 4;
v <<= 2;
}
if (k & 1) {
v = 1 << (k - 1);
if (v < 8) {
for (int j = 0; j < v; ++j) {
mint ajv = a[j] - a[j + v];
a[j] += a[j + v];
a[j + v] = ajv;
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
int j0 = 0;
int j1 = v;
for (; j0 < v; j0 += 8, j1 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
__m256i naj = montgomery_add_256(T0, T1, m2, m0);
__m256i najv = montgomery_sub_256(T0, T1, m2, m0);
_mm256_storeu_si256((__m256i *)(a + j0), naj);
_mm256_storeu_si256((__m256i *)(a + j1), najv);
}
}
}
if (normalize) {
mint invn = modinv(mint(n));
for (int i = 0; i < n; i++) a[i] *= invn;
}
}
__attribute__((target("avx2"))) void inplace_multiply(
int l1, int l2, int zero_padding = true) {
int l = l1 + l2 - 1;
int M = 4;
while (M < l) M <<= 1;
if (zero_padding) {
for (int i = l1; i < M; i++) ntt_inner::_buf1[i] = 0;
for (int i = l2; i < M; i++) ntt_inner::_buf2[i] = 0;
}
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m1 = _mm256_set1_epi32(mod);
const __m256i r = _mm256_set1_epi32(mint::r);
const __m256i N2 = _mm256_set1_epi32(mint::n2);
for (int i = 0; i < l1; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
__m256i b = montgomery_mul_256(a, N2, r, m1);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), b);
}
for (int i = 0; i < l2; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf2 + i));
__m256i b = montgomery_mul_256(a, N2, r, m1);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf2 + i), b);
}
ntt(buf1, M);
ntt(buf2, M);
for (int i = 0; i < M; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
__m256i b = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf2 + i));
__m256i c = montgomery_mul_256(a, b, r, m1);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), c);
}
intt(buf1, M, false);
const __m256i INVM = _mm256_set1_epi32((mint(M).inverse()).a);
for (int i = 0; i < l; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
__m256i b = montgomery_mul_256(a, INVM, r, m1);
__m256i c = my256_mulhi_epu32(my256_mullo_epu32(b, r), m1);
__m256i d = _mm256_and_si256(_mm256_cmpgt_epi32(c, m0), m1);
__m256i e = _mm256_sub_epi32(d, c);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), e);
}
}
void ntt(vector<mint> &a) {
int M = (int)a.size();
for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
ntt(buf1, M);
for (int i = 0; i < M; i++) a[i].a = buf1[i].a;
}
void intt(vector<mint> &a) {
int M = (int)a.size();
for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
intt(buf1, M, true);
for (int i = 0; i < M; i++) a[i].a = buf1[i].a;
}
vector<mint> multiply(const vector<mint> &a, const vector<mint> &b) {
if (a.size() == 0 && b.size() == 0) return vector<mint>{};
int l = a.size() + b.size() - 1;
if (min<int>(a.size(), b.size()) <= 40) {
vector<mint> s(l);
for (int i = 0; i < (int)a.size(); ++i)
for (int j = 0; j < (int)b.size(); ++j) s[i + j] += a[i] * b[j];
return s;
}
assert(l <= ntt_inner::SZ_FFT_BUF);
int M = 4;
while (M < l) M <<= 1;
for (int i = 0; i < (int)a.size(); ++i) buf1[i].a = a[i].a;
for (int i = (int)a.size(); i < M; ++i) buf1[i].a = 0;
for (int i = 0; i < (int)b.size(); ++i) buf2[i].a = b[i].a;
for (int i = (int)b.size(); i < M; ++i) buf2[i].a = 0;
ntt(buf1, M);
ntt(buf2, M);
for (int i = 0; i < M; ++i)
buf1[i].a = mint::reduce(uint64_t(buf1[i].a) * buf2[i].a);
intt(buf1, M, false);
vector<mint> s(l);
mint invm = modinv(mint(M));
for (int i = 0; i < l; ++i) s[i] = buf1[i] * invm;
return s;
}
void ntt_doubling(vector<mint> &a) {
int M = (int)a.size();
for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
intt(buf1, M);
mint r = 1, zeta = modpow(mint(pr),(mint::getmod() - 1) / (M << 1));
for (int i = 0; i < M; i++) buf1[i] *= r, r *= zeta;
ntt(buf1, M);
a.resize(2 * M);
for (int i = 0; i < M; i++) a[M + i].a = buf1[i].a;
}
};
// for garner
static constexpr int m0 = 167772161;
static constexpr int m1 = 469762049;
static constexpr int m2 = 754974721;
using mint0 = MontgomeryModInt<m0>;
using mint1 = MontgomeryModInt<m1>;
using mint2 = MontgomeryModInt<m2>;
static constexpr int r01 = 104391568;
static constexpr int r02 = 323560596;
static constexpr int r12 = 399692502;
static constexpr int r02r12 = 190329765;
static constexpr i64 w1 = m0;
static constexpr i64 w2 = i64(m0) * m1;
using mint998 = MontgomeryModInt<998244353>;
NumberTheoreticTransform<mint998> ntt998;
NumberTheoreticTransform<mint0> ntt0;
NumberTheoreticTransform<mint1> ntt1;
NumberTheoreticTransform<mint2> ntt2;
// small case (T = mint, long long)
template<class T> vector<T> naive_mul
(const vector<T> &A, const vector<T> &B) {
if (A.empty() || B.empty()) return {};
int N = (int)A.size(), M = (int)B.size();
vector<T> res(N + M - 1);
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
res[i + j] += A[i] * B[j];
return res;
}
// mint
template<class mint>
vector<mint> mul(vector<mint> A,vector<mint> B) {
if (A.empty() || B.empty()) return {};
int n = int(A.size()), m = int(B.size());
if (min(n, m) < 30) return naive_mul(A, B);
int MOD = A[0].getmod();
if (MOD == 998244353) {
vector<mint998> a(n),b(m);
for(int i=0;i<n;i++) a[i]=mint998(A[i].get());
for(int i=0;i<m;i++) b[i]=mint998(B[i].get());
vector<mint998> c=ntt998.multiply(a,b);
vector<mint> res(n+m-1);
for(int i=0;i<n+m-1;i++) res[i]=c[i].get();
return res;
}
vector<mint0> a0(n), b0(m);
vector<mint1> a1(n), b1(m);
vector<mint2> a2(n), b2(m);
for (int i = 0; i < n; ++i)
a0[i] = mint0(A[i].get()), a1[i] = mint1(A[i].get()), a2[i] = mint2(A[i].get());
for (int i = 0; i < m; ++i)
b0[i] = mint0(B[i].get()), b1[i] = mint1(B[i].get()), b2[i] = mint2(B[i].get());
static const int W1 = w1%MOD, W2 = w2%MOD;
vector<mint0> c0=ntt0.multiply(a0,b0);
vector<mint1> c1=ntt1.multiply(a1,b1);
vector<mint2> c2=ntt2.multiply(a2,b2);
vector<mint> res(n + m - 1);
for (int i = 0; i < n + m - 1; ++i) {
int n1 = c1[i].get(), n2 = c2[i].get(), a = c0[i].get();
int b = i64(n1 + m1 - a) * r01 % m1;
int c = (i64(n2 + m2 - a) * r02r12 + i64(m2 - b) * r12) % m2;
res[i] = mint(i64(a) + i64(b) * W1 + i64(c) * W2);
}
return res;
}
};
// Formal Power Series
template <typename mint> struct FPS : vector<mint> {
using vector<mint>::vector;
/*
template<class...Args>
FPS(Args...args) : vector<mint>(args...){}
*/
// constructor
FPS(const vector<mint>& r) : vector<mint>(r) {}
// core operator
inline FPS pre(int siz) const {
return FPS(begin(*this), begin(*this) + min((int)this->size(), siz));
}
inline FPS rev() const {
FPS res = *this;
reverse(begin(res), end(res));
return res;
}
inline FPS& normalize() {
while (!this->empty() && this->back() == 0) this->pop_back();
return *this;
}
// basic operator
inline FPS operator - () const noexcept {
FPS res = (*this);
for (int i = 0; i < (int)res.size(); ++i) res[i] = -res[i];
return res;
}
inline void ntt() {
NTT::ntt998.ntt(*this);
}
inline void intt() {
NTT::ntt998.intt(*this);
}
inline void ntt_doubling(){
NTT::ntt998.ntt_doubling(*this);
}
//*/
inline FPS operator + (const mint& v) const { return FPS(*this) += v; }
inline FPS operator + (const FPS& r) const { return FPS(*this) += r; }
inline FPS operator - (const mint& v) const { return FPS(*this) -= v; }
inline FPS operator - (const FPS& r) const { return FPS(*this) -= r; }
inline FPS operator * (const mint& v) const { return FPS(*this) *= v; }
inline FPS operator * (const FPS& r) const { return FPS(*this) *= r; }
inline FPS operator / (const mint& v) const { return FPS(*this) /= v; }
inline FPS operator << (int x) const { return FPS(*this) <<= x; }
inline FPS operator >> (int x) const { return FPS(*this) >>= x; }
inline FPS& operator += (const mint& v) {
if (this->empty()) this->resize(1);
(*this)[0] += v;
return *this;
}
inline FPS& operator += (const FPS& r) {
if (r.size() > this->size()) this->resize(r.size());
for (int i = 0; i < (int)r.size(); ++i) (*this)[i] += r[i];
return this->normalize();
}
inline FPS& operator -= (const mint& v) {
if (this->empty()) this->resize(1);
(*this)[0] -= v;
return *this;
}
inline FPS& operator -= (const FPS& r) {
if (r.size() > this->size()) this->resize(r.size());
for (int i = 0; i < (int)r.size(); ++i) (*this)[i] -= r[i];
return this->normalize();
}
inline FPS& operator *= (const mint& v) {
for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= v;
return *this;
}
inline FPS& operator *= (const FPS& r) {
return *this = NTT::ntt998.multiply((*this), r);
}
inline FPS& operator /= (const mint& v) {
assert(v != 0);
mint iv = modinv(v);
for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= iv;
return *this;
}
inline FPS& operator <<= (int x) {
FPS res(x, 0);
res.insert(res.end(), begin(*this), end(*this));
return *this = res;
}
inline FPS& operator >>= (int x) {
FPS res;
res.insert(res.end(), begin(*this) + x, end(*this));
return *this = res;
}
inline mint eval(const mint& v){
mint res = 0;
for (int i = (int)this->size()-1; i >= 0; --i) {
res *= v;
res += (*this)[i];
}
return res;
}
inline friend FPS gcd(const FPS& f, const FPS& g) {
if (g.empty()) return f;
return gcd(g, f % g);
}
// advanced operation
// df/dx
inline friend FPS diff(const FPS& f) {
int n = (int)f.size();
FPS res(n-1);
for (int i = 1; i < n; ++i) res[i-1] = f[i] * i;
return res;
}
// \int f dx
inline friend FPS integrate(const FPS& f) {
int n = (int)f.size();
FPS res(n+1, 0);
for (int i = 0; i < n; ++i) res[i+1] = f[i] / (i+1);
return res;
}
// inv(f), f[0] must not be 0
/*inline friend FPS inv(const FPS& f, int deg) {
assert(f[0] != 0);
if (deg < 0) deg = (int)f.size();
FPS res({mint(1) / f[0]});
for (int i = 1; i < deg; i <<= 1) {
res = (res + res - res * res * f.pre(i << 1)).pre(i << 1);
}
res.resize(deg);
return res;
}
//*/
inline friend FPS inv(const FPS& f, int deg) {
assert(f[0]!=mint(0));
if (deg < 0) deg = (int)f.size();
FPS res(deg);
res[0] = {mint(1)/f[0]};
for (int d = 1; d < deg; d<<=1) {
FPS g(2*d), h(2*d);
for (int j = 0; j < min((int)f.size(),2*d); j++) g[j] = f[j];
for (int j = 0; j < d; j++) h[j] = res[j];
g.ntt();
h.ntt();
for (int j = 0; j < 2*d; j++) g[j]*=h[j];
g.intt();
for (int j = 0; j < d; j++) g[j]=0;
g.ntt();
for (int j = 0; j < 2*d; j++) g[j]*=h[j];
g.intt();
for (int j = d; j < min(2*d, deg); j++) res[j] = -g[j];
}
return res.pre(deg);
}
//*/
inline friend FPS inv(const FPS& f) {
return inv(f, f.size());
}
// division, r must be normalized (r.back() must not be 0)
inline FPS& operator /= (const FPS& r) {
const int n=(*this).size(),m=r.size();
if(n<m){
(*this).clear();
return *this;
}
assert(r.back() != 0);
this->normalize();
if (this->size() < r.size()) {
this->clear();
return *this;
}
int need = (int)this->size() - (int)r.size() + 1;
*this = ((*this).rev().pre(need) * inv(r.rev(), need)).pre(need).rev();
return *this;
}
inline FPS& operator %= (const FPS &r) {
const int n=(*this).size(),m=r.size();
if(n<m) return (*this);
assert(r.back() != 0);
this->normalize();
FPS q = (*this) / r;
return *this -= q * r;
}
inline FPS operator / (const FPS& r) const { return FPS(*this) /= r; }
inline FPS operator % (const FPS& r) const { return FPS(*this) %= r; }
// log(f) = \int f'/f dx, f[0] must be 1
inline friend FPS log(const FPS& f, int deg) {
assert(f[0] == 1);
FPS res = integrate((diff(f) * inv(f, deg)).pre(deg-1));
return res;
}
inline friend FPS log(const FPS& f) {
return log(f, f.size());
}
// exp(f), f[0] must be 0
/*inline friend FPS exp(const FPS& f, int deg) {
assert(f[0] == 0);
FPS res(1, 1);
for (int i = 1; i < deg; i <<= 1) {
res = res * (f.pre(i<<1) - log(res, i<<1) + 1).pre(i<<1);
}
res.resize(deg);
return res;
}
//*/
inline friend FPS exp(const FPS& f, int deg) {
assert(f.size()==0 || f[0]==mint(0));
if(deg<0) deg=(int)f.size();
FPS rf;
rf.reserve(deg+1);
rf.push_back(mint(0));
rf.push_back(mint(1));
auto inplace_integral = [&](FPS& F) -> void{
const int n=(int)F.size();
auto MOD=mint::getmod();
while((int)rf.size()<=n){
int i=rf.size();
rf.push_back((-rf[MOD%i])*(MOD/i));
}
F.insert(begin(F),mint(0));
for(int i=1;i<=n;i++) F[i]*=rf[i];
};
auto inplace_diff = [&](FPS& F) -> void{
if(F.empty()) return;
F.erase(begin(F));
mint coeff=1,one=1;
for(int i=0;i<(int)F.size();i++){
F[i]*=coeff;
coeff+=one;
}
};
FPS b{1,(1<(int)f.size()?f[1]:0)},c{1},z1,z2{1,1};
for(int m=2;m<deg;m<<=1){
auto y=b;
y.resize(2*m);
y.ntt();
z1=z2;
FPS z(m);
for(int i=0;i<m;i++) z[i]=y[i]*z1[i];
z.intt();
fill(begin(z),begin(z)+m/2,mint(0));
z.ntt();
for(int i=0;i<m;i++) z[i]*=-z1[i];
z.intt();
c.insert(end(c),begin(z)+m/2,end(z));
z2=c;
z2.resize(2*m);
z2.ntt();
FPS x(begin(f),begin(f)+min((int)f.size(),m));
x.resize(m);
inplace_diff(x);
x.push_back(mint(0));
x.ntt();
for(int i=0;i<m;i++) x[i]*=y[i];
x.intt();
x-=diff(b);
x.resize(2*m);
for(int i=0;i<m-1;i++) x[m+i]=x[i],x[i]=mint(0);
x.ntt();
for(int i=0;i<2*m;i++) x[i]*=z2[i];
x.intt();
x.pop_back();
inplace_integral(x);
for(int i=m;i<min((int)f.size(),2*m);i++) x[i]+=f[i];
fill(begin(x),begin(x)+m,mint(0));
x.ntt();
for(int i=0;i<2*m;i++) x[i]*=y[i];
x.intt();
b.insert(end(b),begin(x)+m,end(x));
}
return FPS{begin(b),begin(b)+deg};
}
inline friend FPS exp(const FPS& f) {
return exp(f, f.size());
}
// pow(f) = exp(e * log f)
inline friend FPS pow(const FPS& f, long long e, int deg) {
long long i = 0;
if(e==0){
FPS res(deg);
res[0]=1;
return res;
}
while (i < (int)f.size() && f[i] == 0 && i * e < deg) ++i;
if (i == (int)f.size()) return FPS(deg, 0);
if (i * e >= deg) return FPS(deg, 0);
mint k = f[i];
FPS res = exp(log((f >> i) / k, deg) * mint(e), deg) * modpow(k, e) << (e * i);
res.resize(deg);
return res;
}
inline friend FPS pow(const FPS& f, long long e) {
return pow(f, e, f.size());
}
// sqrt(f), f[0] must be 1
inline friend FPS sqrt_base(const FPS& f, int deg) {
assert(f[0] == 1);
mint inv2 = mint(1) / 2;
FPS res(1, 1);
for (int i = 1; i < deg; i <<= 1) {
res = (res + f.pre(i << 1) * inv(res, i << 1)).pre(i << 1);
for (mint& x : res) x *= inv2;
}
res.resize(deg);
return res;
}
inline friend FPS sqrt_base(const FPS& f) {
return sqrt_base(f, f.size());
}
FPS taylor_shift(mint c) const {
int n = (int) this->size();
vector<mint> fact(n), rfact(n);
fact[0] = rfact[0] = mint(1);
for(int i = 1; i < n; i++) fact[i] = fact[i - 1] * mint(i);
rfact[n - 1] = mint(1) / fact[n - 1];
for(int i = n - 1; i > 1; i--) rfact[i - 1] = rfact[i] * mint(i);
FPS p(*this);
for(int i = 0; i < n; i++) p[i] *= fact[i];
p = p.rev();
FPS bs(n, mint(1));
for(int i = 1; i < n; i++) bs[i] = bs[i - 1] * c * rfact[i] * fact[i - 1];
p = (p * bs).pre(n);
p = p.rev();
for(int i = 0; i < n; i++) p[i] *= rfact[i];
return p;
}
};
namespace NTT{
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_mod_2(int x) { return __builtin_parity(x); }
int popcnt_mod_2(u32 x) { return __builtin_parity(x); }
int popcnt_mod_2(ll x) { return __builtin_parityll(x); }
int popcnt_mod_2(u64 x) { return __builtin_parityll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
fft_info<MontgomeryModInt<998244353>> info998;
constexpr auto bcl(int x){
return (x<2)?1:2<<std::__lg(x-1);
}
template <typename mint>
struct DODFT{
fft_info<mint> INFO;
int fft_len=0;
mint _g=INFO.g;
std::vector<mint> _w{1},iw{1},_w22{1},iw22{1};
auto init_w(int lm){
_w.resize(lm),iw.resize(lm),_w22.resize(lm),iw22.resize(lm);
for(auto i=1;i<lm;i<<=1){
_w[i]=modpow(_g,((mint::getmod()-1)>>2)/i);
iw[i]=modpow(_g,mint::getmod()-1-((mint::getmod()-1)>>2)/i);
}
for(auto i=1;i<lm;++i){
_w[i]=_w[i&(i-1)]*_w[i&-i];
iw[i]=iw[i&(i-1)]*iw[i&-i];
}
for(auto i=1,i2=2;i<lm;i=i2,i2<<=1){
mint _G=modpow(_g,(mint::getmod()-1)/i2),_r=mint::getmod()-(mint::getmod()-1)/i;
mint iG=modpow(_G,mint::getmod()-2),ir=mint::getmod()-(mint::getmod()-1)/i;
for(auto j=i;j<i2;++j){
_w22[j]=_r,_r=_r*_G;
iw22[j]=ir,ir=ir*iG;
}
}
}
inline auto chk_w(int lm){
if((lm>>=1)>int(_w.size())){
init_w(lm);
}
}
inline auto rot_R(mint*f,int L,mint r){
for(auto i=0;i<L;++i){
auto x=f[i],y=f[i+L]*r;
f[i]=x+y,f[i+L]=x-y;
}
}
inline auto rot_L(mint*f,int L,mint r){
for(auto i=0;i<L;++i){
auto x=f[i],y=f[i+L];
f[i]=x+y,f[i+L]=(x-y)*r;
}
}
inline auto rrot_R(mint*f,int L,int lm){
for(auto j=0,k=0;j<lm;j+=L*2,++k){
rot_R(f+j,L,_w[k]);
}
}
inline auto rrot_L(mint*f,int L,int lm){
for(auto j=0,k=0;j<lm;j+=L*2,++k){
rot_L(f+j,L,iw[k]);
}
}
auto dif(mint*f,int lm){
fft_len+=lm;
chk_w(lm);
for(auto L=lm>>1;L;L>>=1){
rrot_R(f,L,lm);
}
}
auto fft_2D(mint*f,int n,int m){
auto lm=n*m;
fft_len+=lm;
chk_w(lm);
for(auto j=0;j<lm;j+=m){
for(auto L=m>>1;L;L>>=1){
rrot_R(f+j,L,m);
}
}
for(auto L=lm>>1;L>=m;L>>=1){
rrot_R(f,L,lm);
}
}
auto dit(mint*f,int lm){
fft_len+=lm;
for(auto L=1;L<lm;L<<=1){
rrot_L(f,L,lm);
}
}
template<bool fx=true>auto ifft_2D(mint*f,int n,int m){
auto lm=n*m;
fft_len+=lm;
for(auto j=0;j<lm;j+=m){
for(auto L=1;L<m;L<<=1){
rrot_L(f+j,L,m);
}
}
for(auto L=m;L<lm;L<<=1){
rrot_L(f,L,lm);
}
if constexpr(fx){
const mint iv=mint::getmod()-(mint::getmod()-1)/lm;
for(auto i=0;i<lm;++i){
f[i]=f[i]*iv;
}
}
}
inline auto dot(mint*f,const mint*g,int lm){
for(auto i=0;i<lm;++i){
f[i]=f[i]*g[i];
}
}
inline auto rdot(const mint*f,const mint*g,mint*h,int lm){
for(auto i=0;i<lm;++i){
h[i]=f[i]*g[i];
}
}
void __PowerYX(mint*P,mint*tQ,int n,int m,mint&OneP,mint&OneQ){
if(m==1){
dif(P,n);
for(int i=n-1;i>=0;--i){
mint x=P[i];
P[i*2]=x,P[i*2+1]=x;
}
return;
}
mint*Q=new mint[4*n*m];
if(n==1){
for(int i=0;i<m;++i){Q[i]=-tQ[i];}
std::fill(Q+m,Q+m*2,0),dif(Q,m*2);
std::fill(Q+m*2,Q+m*4,1),rot_R(Q,m*2,1);
}
else{
fft_len += 4*n*m;
for(int i=0;i<2*n*m;++i){
Q[i]=tQ[i*2]*tQ[i*2+1];
}
OneQ=OneQ*OneQ;
for(auto i=0;i<n;++i){
auto dft=Q+i*m*2;
for(auto L=1;L<=m;L<<=1){
rrot_L(dft,L,m*2);
}
std::fill_n(dft+m,m,0);
for(auto L=m;L;L>>=1){
rrot_R(dft,L,m*2);
}
}
auto g=Q+2*n*m;
std::copy(Q,g,g);
for(auto L=m*2;L<=n*m;L<<=1){
rrot_L(g,L,2*n*m);
}
for(int j=0,k=0,diff=n;j<n*m*2;j+=m*2,++k){
for(int i=0;i<m*2;++i){
g[j+i]=g[j+i]*_w22[diff+k];
}
}
OneQ=OneQ*m*2;
mint Two=OneQ+OneQ;
for(int i=0;i<m*2;++i){
g[i]=g[i]-Two;
}
for(auto L=n*m;L>m;L>>=1){
rrot_R(g,L,2*n*m);
}
}
const mint oo=OneQ;
__PowerYX(P,Q,n*2,m/2,OneP,OneQ);
for(int i=0;i<2*n*m;++i){
auto x=Q[i*2],y=Q[i*2+1];
Q[i*2]=P[i]*y;
Q[i*2+1]=P[i]*x;
}
OneP=OneP*oo;
if(n==1){
ifft_2D<false>(Q,2*n,2*m);
mint fx=modinv(OneP*n*m*4);
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
P[i*m+j]=Q[(i+n)*(2*m)+j]*fx;
}
}
}
else{
fft_len += 4*n*m;
auto g=Q+2*n*m;
for(auto L=2*m;L<=n*m;L<<=1){
rrot_L(g,L,2*n*m);
}
for(int j=0,k=0,diff=n;j<n*m*2;j+=m*2,++k){
for(int i=0;i<m*2;++i){
g[j+i]=g[j+i]*iw22[diff+k];
}
}
for(auto L=n*m;L>m;L>>=1){
rrot_R(g,L,2*n*m);
}
OneP=OneP*2;
for(auto i=0;i<2*n*m;++i){
P[i]=Q[i]-g[i];
}
for(auto i=0;i<n;++i){
auto dft=P+i*m*2;
for(auto L=1;L<=m;L<<=1){
rrot_L(dft,L,m*2);
}
std::fill_n(dft+m,m,0);
for(auto L=m;L;L>>=1){
rrot_R(dft,L,m*2);
}
}
OneP=OneP*m*2;
}
delete []Q;
}
vector<mint> fac{1},ifac{1},iv{0};
auto init_fac(int n){
fac.resize(n),ifac.resize(n),iv.resize(n);
for(auto i=1;i<n;++i){fac[i]=fac[i-1]*i;}
ifac[n-1]=modinv(fac[n-1]);
for(auto i=n-1;i>0;--i){ifac[i-1]=ifac[i]*i,iv[i]=ifac[i]*fac[i-1];}
}
inline auto chk_fac(int n){
if(n>int(fac.size())){
init_fac(std::max(n,int(fac.size())*2));
}
}
vector<mint> Ax,Bx,Cx,Dx;
inline auto toBuf(vector<mint>&f,int lm){
f.resize(lm);
return f.data();
}
mint iv4=modinv(mint(4));
auto Inv(const mint*f,mint*g,int n){
g[0]=modinv(f[0]);
auto lm=bcl(n);
auto ax=toBuf(Ax,lm),bx=toBuf(Bx,lm);
mint fx=mint::getmod()-iv4.get();
for(auto t=2,m=1;t<=lm;m=t,t<<=1,fx=fx*iv4){
auto xl=std::min(t,n);
std::fill(std::copy_n(f,xl,ax),ax+t,0),std::fill(std::copy_n(g,m,bx),bx+t,0);
dif(ax,t),dif(bx,t),dot(ax,bx,t),dit(ax,t),std::fill_n(ax,m,0),dif(ax,t),dot(ax,bx,t),dit(ax,t);
for(auto i=m;i<xl;++i){g[i]=ax[i]*fx;}
}
}
auto Quo(const mint*f,const mint*g,mint*h,int n){
//if(n==1){*h=*f*modinv(*g);return;}
if(n==1){h[0]=f[0]*modinv(g[0]);return;}
auto lm=bcl(n),hl=lm>>1;
const mint iv=mint::getmod()-(mint::getmod()-1)/lm;
auto ax=toBuf(Ax,lm),bx=toBuf(Bx,lm),cx=toBuf(Cx,lm);
Inv(g,cx,hl),std::fill_n(cx+hl,hl,0),dif(cx,lm),std::fill(std::copy_n(f,hl,ax),ax+lm,0),dif(ax,lm),dot(ax,cx,lm),dit(ax,lm);
for(auto i=0;i<hl;++i){h[i]=ax[i]=ax[i]*iv;}
std::fill_n(ax+hl,hl,0),dif(ax,lm),std::fill(std::copy_n(g,n,bx),bx+lm,0),dif(bx,lm),dot(ax,bx,lm),dit(ax,lm),std::fill_n(ax,hl,0);
for(auto i=hl;i<n;++i){ax[i]=ax[i]*iv-f[i];}
dif(ax,lm),dot(ax,cx,lm),dit(ax,lm);
const mint _iv=-iv;
for(auto i=hl;i<n;++i){h[i]=ax[i]*_iv;}
}
auto Ln(const mint*f,mint*g,int n){
auto dx=toBuf(Dx,n);
for(auto i=0;i<n;++i){
dx[i]=f[i]*i;
}
Quo(dx,f,g,n),dot(g,iv.data(),n);
}
auto Exp(const mint*f,mint*g,int n){
auto lm=bcl(n);
auto ax=toBuf(Ax,lm),bx=toBuf(Bx,lm),cx=toBuf(Cx,lm),dx=toBuf(Dx,lm);
g[0]=dx[0]=ax[0]=ax[1]=1;
auto fx=-iv4;
for(auto t2=4,t=2,m=1;t<=lm;m=t,t=t2,t2<<=1,fx=fx*iv4){
auto xl=min(t,n);
for(auto i=0;i<m;++i){cx[i]=f[i]*i;}
dif(cx,m),dot(cx,ax,m),dit(cx,m);
const mint IV=(mint::getmod()-1)/m;
for(auto i=0;i<m;++i){cx[m+i]=g[i]*i+cx[i]*IV,cx[i]=0;}
dif(cx,t),std::fill(std::copy(dx,dx+m,bx),bx+t,0),dif(bx,t),dot(cx,bx,t),dit(cx,t);
const mint Iv=(mint::getmod()-1)/t;
for(int i=m;i<t;++i){cx[i]=cx[i]*Iv*iv[i]+f[i],cx[i-m]=0;}
dif(cx,t),dot(cx,ax,t),dit(cx,t);
const mint iv=-Iv;
for(int i=m;i<xl;++i){g[i]=cx[i]*iv;}
if(t!=lm){
std::fill(std::copy_n(g,t,ax),ax+t2,0),dif(ax,t2),rdot(ax,bx,cx,t),dit(cx,t);
for(auto i=m;i<t;++i){cx[i]=cx[i]*fx,cx[i-m]=0;}
dif(cx,t),dot(cx,bx,t),dit(cx,t),std::copy(cx+m,cx+t,dx+m);
}
}
}
vector<mint> __PowerXY(vector<mint> g,int n){
vector<mint> dftP(4*n,1),dftQ(4*n);for(auto i=0;i<n;++i){dftQ[i]=-g[i];}chk_w(n*2);for(auto L=n;L;L>>=1){rrot_R(dftQ.data(),L,n*2);}std::fill(dftQ.begin()+n*2,dftQ.end(),1);rot_R(dftQ.data(),n*2,1);auto k=1,t=n;mint One=1;for(;;t>>=1,k<<=1){for(auto i=0;i<2*k;++i){for(auto j=0;j<2*t;j+=2){auto p=i*(2*t)+j,q=i*t+j/2;auto x=dftQ[p],y=dftQ[p+1];dftP[q]=(dftP[p]*y-dftP[p+1]*x)*iw[j/2];dftQ[q]=x*y;}}One=One*One;if(t==2){ifft_2D<false>(dftP.data(),2*k,t);const mint fx=modinv(One*mint(n*2));for(auto i=0;i<n;++i){dftP[i]=fx*dftP[i<<1];}dftP.resize(n);break;}else{fft_len += 8*n;{for(auto i=0;i<2*k;++i){auto dft=dftP.data()+i*t;for(auto L=1;L<t;L<<=1){rrot_L(dft,L,t);}std::fill(dft+t/2,dft+t,0);for(auto L=t>>1;L;L>>=1){rrot_R(dft,L,t);}}auto g=dftP.data()+2*n;std::copy(dftP.cbegin(),dftP.cbegin()+2*n,g);for(auto L=t;L<n*2;L<<=1){rrot_L(g,L,n*2);}for(int j=0,k=0,diff=(n*2)/t;j<n*2;j+=t,++k){for(int i=0;i<t;++i){g[j+i]=g[j+i]*_w22[diff+k];}}for(auto L=n;L>=t;L>>=1){rrot_R(g,L,n*2);}}{for(auto i=0;i<2*k;++i){auto dft=dftQ.data()+i*t;for(auto L=1;L<t;L<<=1){rrot_L(dft,L,t);}std::fill(dft+t/2,dft+t,0);for(auto L=t>>1;L;L>>=1){rrot_R(dft,L,t);}}auto g=dftQ.data()+2*n;std::copy(dftQ.cbegin(),dftQ.cbegin()+2*n,g);for(auto L=t;L<n*2;L<<=1){rrot_L(g,L,n*2);}for(int j=0,k=0,diff=(n*2)/t;j<n*2;j+=t,++k){for(int i=0;i<t;++i){g[j+i]=g[j+i]*_w22[diff+k];}}One=One*t;mint Two=One+One;for(int i=0;i<t;++i){g[i]=g[i]-Two;}for(auto L=n;L>=t;L>>=1){rrot_R(g,L,n*2);}}}}
return dftP;
}
};
DODFT<MontgomeryModInt<998244353>> ddft998;
}
template <typename mint>
FPS<mint> composition(FPS<mint> f,FPS<mint> g){
int n=f.size();
auto lm=NTT::bcl(std::max<int>(f.size(),n));
f.resize(lm),g.resize(lm);
if(g[0]!=mint(0)){
f=f.taylor_shift(g[0]);
g[0]=0;
}
if(lm!=1){
f.resize(lm*2);
mint op=1,oq=1;
NTT::ddft998.__PowerYX(f.data(),g.data(),1,lm,op,oq);
}
f.resize(n);
return f;
}
template <typename mint>
FPS<mint> compositional_inverse(FPS<mint> g){
int n=g.size();
int lm=NTT::bcl(n);
g.resize(lm);
mint v=modinv(g[1]);
for(auto&x:g){x=x*v;}
auto G=NTT::ddft998.__PowerXY(g,lm);
NTT::ddft998.chk_fac(lm);
mint fx=1;
for(int i=0;i<lm;++i){
g[i]=fx*NTT::ddft998.iv[lm-i-1]*G[i]*(lm-1);
fx=fx*v;
}
NTT::ddft998.Ln(g.data(),G.data(),lm);
for(auto&x:G){x=x*mint(mint::getmod()-NTT::ddft998.iv[lm-1].get());}
NTT::ddft998.Exp(G.data(),g.data()+1,lm-1),g[0]=0;
for(int i=1;i<lm;++i){g[i]=g[i]*v;}
g.resize(n);
return g;
}
using mint=MontgomeryModInt<998244353>;
int main(){
#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,m;
cin >> n >> m;
m--;
FPS<mint> f(n+2),g(n+2);
f[1]=1,f[2]=1;
g[1]=1,g[2]=1;
while(m){
if(m&1) f=composition(g,f);
g=composition(g,g);
m>>=1;
}
cout << f[n+1].get() << endl;
}