結果
| 問題 | No.3574 Sum of Mex |
| コンテスト | |
| ユーザー |
 noya2
|
| 提出日時 | 2026-06-19 23:25:23 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,883 ms / 2,000 ms |
| コード長 | 63,458 bytes |
| 記録 | |
| コンパイル時間 | 4,120 ms |
| コンパイル使用メモリ | 369,588 KB |
| 実行使用メモリ | 245,908 KB |
| 最終ジャッジ日時 | 2026-06-19 23:25:32 |
| 合計ジャッジ時間 | 7,006 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 11 |
ソースコード
#line 2 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"
using namespace std;
#include<bits/stdc++.h>
#line 1 "/Users/noya2/Desktop/Noya2_library/template/inout_old.hpp"
namespace noya2 {
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
os << p.first << " " << p.second;
return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p){
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
int s = (int)v.size();
for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v){
for (auto &x : v) is >> x;
return is;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &...u){
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u){
cout << t;
if (sizeof...(u)) cout << sep;
out(u...);
}
template<typename T>
void out(const vector<vector<T>> &vv){
int s = (int)vv.size();
for (int i = 0; i < s; i++) out(vv[i]);
}
struct IoSetup {
IoSetup(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(7);
}
} iosetup_noya2;
} // namespace noya2
#line 1 "/Users/noya2/Desktop/Noya2_library/template/const.hpp"
namespace noya2{
const int iinf = 1'000'000'007;
const long long linf = 2'000'000'000'000'000'000LL;
const long long mod998 = 998244353;
const long long mod107 = 1000000007;
const long double pi = 3.14159265358979323;
const vector<int> dx = {0,1,0,-1,1,1,-1,-1};
const vector<int> dy = {1,0,-1,0,1,-1,-1,1};
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string NUM = "0123456789";
void yes(){ cout << "Yes\n"; }
void no(){ cout << "No\n"; }
void YES(){ cout << "YES\n"; }
void NO(){ cout << "NO\n"; }
void yn(bool t){ t ? yes() : no(); }
void YN(bool t){ t ? YES() : NO(); }
} // namespace noya2
#line 2 "/Users/noya2/Desktop/Noya2_library/template/utils.hpp"
#line 6 "/Users/noya2/Desktop/Noya2_library/template/utils.hpp"
namespace noya2{
unsigned long long inner_binary_gcd(unsigned long long a, unsigned long long b){
if (a == 0 || b == 0) return a + b;
int n = __builtin_ctzll(a); a >>= n;
int m = __builtin_ctzll(b); b >>= m;
while (a != b) {
int mm = __builtin_ctzll(a - b);
bool f = a > b;
unsigned long long c = f ? a : b;
b = f ? b : a;
a = (c - b) >> mm;
}
return a << std::min(n, m);
}
template<typename T> T gcd_fast(T a, T b){ return static_cast<T>(inner_binary_gcd(std::abs(a),std::abs(b))); }
long long sqrt_fast(long long n) {
if (n <= 0) return 0;
long long x = sqrt(n);
while ((x + 1) * (x + 1) <= n) x++;
while (x * x > n) x--;
return x;
}
template<typename T> T floor_div(const T n, const T d) {
assert(d != 0);
return n / d - static_cast<T>((n ^ d) < 0 && n % d != 0);
}
template<typename T> T ceil_div(const T n, const T d) {
assert(d != 0);
return n / d + static_cast<T>((n ^ d) >= 0 && n % d != 0);
}
template<typename T> void uniq(std::vector<T> &v){
std::sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T> inline bool range(T l, T x, T r){ return l <= x && x < r; }
} // namespace noya2
#line 8 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define repp(i,m,n) for (int i = (m); i < (int)(n); i++)
#define reb(i,n) for (int i = (int)(n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
namespace noya2{
/* ~ (. _________ . /) */
}
using namespace noya2;
#line 2 "c.cpp"
#line 2 "/Users/noya2/Desktop/Noya2_library/utility/modint.hpp"
#line 4 "/Users/noya2/Desktop/Noya2_library/utility/modint.hpp"
#line 2 "/Users/noya2/Desktop/Noya2_library/math/prime.hpp"
#line 4 "/Users/noya2/Desktop/Noya2_library/math/prime.hpp"
namespace noya2 {
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime_flag = is_prime_constexpr(n);
// {gcd(a, b), a^{-1} mod b}
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u;
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(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 (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root_flag = primitive_root_constexpr(m);
// constexpr long long primitive_root_constexpr(long long m){
// if (m == (1LL << 47) - (1LL << 24) + 1) return 3;
// return primitive_root_constexpr(static_cast<int>(m));
// }
} // namespace noya2
#line 6 "/Users/noya2/Desktop/Noya2_library/utility/modint.hpp"
namespace noya2{
struct barrett {
unsigned int _m;
unsigned long long im;
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
unsigned int umod() const { return _m; }
unsigned int mul(unsigned int a, unsigned int b) const {
unsigned long long z = a;
z *= b;
unsigned long long x = (unsigned long long)((__uint128_t(z) * im) >> 64);
unsigned int v = (unsigned int)(z - x * _m);
if (_m <= v) v += _m;
return v;
}
};
template <int m>
struct static_modint {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
constexpr static_modint() : _v(0) {}
template<std::signed_integral T>
constexpr static_modint(T v){
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template<std::unsigned_integral T>
constexpr static_modint(T v){
_v = (unsigned int)(v % umod());
}
constexpr unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
constexpr mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
constexpr mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
constexpr mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
constexpr mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
constexpr mint operator+() const { return *this; }
constexpr mint operator-() const { return mint() - *this; }
constexpr mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
constexpr mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend constexpr mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend constexpr mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend constexpr mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend constexpr mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend constexpr bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend constexpr bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
friend std::ostream &operator<<(std::ostream &os, const mint& p) {
return os << p.val();
}
friend std::istream &operator>>(std::istream &is, mint &a) {
long long t; is >> t;
a = mint(t);
return (is);
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = is_prime_flag<m>;
};
template <int id> struct dynamic_modint {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template<std::signed_integral T>
dynamic_modint(T v){
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template<std::unsigned_integral T>
dynamic_modint(T v){
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = noya2::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
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._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
friend std::ostream &operator<<(std::ostream &os, const mint& p) {
return os << p.val();
}
friend std::istream &operator>>(std::istream &is, mint &a) {
long long t; is >> t;
a = mint(t);
return (is);
}
private:
unsigned int _v;
static barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> noya2::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
template<typename T>
concept Modint = requires (T &a){
T::mod();
a.inv();
a.val();
a.pow(declval<int>());
};
} // namespace noya2
#line 4 "c.cpp"
using mint = modint998244353;
#line 2 "/Users/noya2/Desktop/Noya2_library/math/binomial.hpp"
#line 4 "/Users/noya2/Desktop/Noya2_library/math/binomial.hpp"
namespace noya2 {
template<typename mint>
struct binomial {
binomial(int len = 300000){ extend(len); }
static mint fact(int n){
if (n < 0) return 0;
while (n >= (int)_fact.size()) extend();
return _fact[n];
}
static mint ifact(int n){
if (n < 0) return 0;
while (n >= (int)_fact.size()) extend();
return _ifact[n];
}
static mint inv(int n){
return ifact(n) * fact(n-1);
}
static mint C(int n, int r){
if (!(0 <= r && r <= n)) return 0;
return fact(n) * ifact(r) * ifact(n-r);
}
static mint P(int n, int r){
if (!(0 <= r && r <= n)) return 0;
return fact(n) * ifact(n-r);
}
static mint catalan(int n){
return C(n * 2, n) * inv(n + 1);
}
inline mint operator()(int n, int r) { return C(n, r); }
template<class... Cnts>
static mint M(const Cnts&... cnts){
return multinomial(0,1,cnts...);
}
static void initialize(int len = 2){
_fact.clear();
_ifact.clear();
_fact = {1,1};
_ifact = {1,1};
extend(len);
}
private:
static mint multinomial(const int& sum, const mint& div_prod){
if (sum < 0) return 0;
return fact(sum) * div_prod;
}
template<class... Tail>
static mint multinomial(const int& sum, const mint& div_prod, const int& n1, const Tail&... tail){
if (n1 < 0) return 0;
return multinomial(sum+n1,div_prod*ifact(n1),tail...);
}
static std::vector<mint> _fact, _ifact;
static void extend(int len = -1){
int siz = _fact.size();
if (siz == 0){
_fact = {1,1};
_ifact = {1,1};
siz = _fact.size();
}
if (len == -1) len = siz * 2;
len = (int)min<long long>(len, mint::mod() - 1);
if (len < siz) return ;
_fact.resize(len+1), _ifact.resize(len+1);
for (int i = siz; i <= len; i++) _fact[i] = _fact[i-1] * i;
assert(_fact[len].val() != 0);
_ifact[len] = _fact[len].inv();
for (int i = len; i > siz; i--) _ifact[i-1] = _ifact[i] * i;
}
};
template<typename mint> std::vector<mint> noya2::binomial<mint>::_fact = {1,1};
template<typename mint> std::vector<mint> noya2::binomial<mint>::_ifact = {1,1};
} // namespace noya2
#line 6 "c.cpp"
binomial<mint> bnm;
#line 2 "/Users/noya2/Desktop/Noya2_library/fps998244353/fps998244353.hpp"
#line 4 "/Users/noya2/Desktop/Noya2_library/fps998244353/fps998244353.hpp"
#line 2 "/Users/noya2/Desktop/Noya2_library/fps998244353/ntt998244353.hpp"
#line 2 "/Users/noya2/Desktop/Noya2_library/fps998244353/modint998244353.hpp"
#line 4 "/Users/noya2/Desktop/Noya2_library/fps998244353/modint998244353.hpp"
#line 6 "/Users/noya2/Desktop/Noya2_library/fps998244353/modint998244353.hpp"
namespace noya2 {
template <>
struct static_modint<998244353> {
using mint = static_modint;
public:
static constexpr int mod() { return 998244353; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
constexpr static_modint() : _v(0) {}
template<std::signed_integral T>
constexpr static_modint(T v){
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template<std::unsigned_integral T>
constexpr static_modint(T v){
_v = (unsigned int)(v % umod());
}
constexpr unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
constexpr mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
constexpr mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
constexpr mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
constexpr mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
constexpr mint operator+() const { return *this; }
constexpr mint operator-() const { return mint() - *this; }
constexpr mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
constexpr mint inv() const {
assert(_v);
return pow(umod() - 2);
}
friend constexpr mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend constexpr mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend constexpr mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend constexpr mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend constexpr bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend constexpr bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
friend std::ostream &operator<<(std::ostream &os, const mint& p) {
return os << p.val();
}
friend std::istream &operator>>(std::istream &is, mint &a) {
long long t; is >> t;
a = mint(t);
return (is);
}
unsigned int _v;
static constexpr int primitive_root_constexpr_v = 3;
private:
static constexpr unsigned int umod() { return 998244353u; }
static constexpr bool prime = true;
};
} // namespace noya2
#line 4 "/Users/noya2/Desktop/Noya2_library/fps998244353/ntt998244353.hpp"
#line 7 "/Users/noya2/Desktop/Noya2_library/fps998244353/ntt998244353.hpp"
namespace noya2 {
namespace internal {
constexpr int FFT_MAX = 23;
constexpr unsigned FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 911660635U, 372528824U, 929031873U, 452798380U, 922799308U, 781712469U, 476477967U, 166035806U, 258648936U, 584193783U, 63912897U, 350007156U, 666702199U, 968855178U, 629671588U, 24514907U, 996173970U, 363395222U, 565042129U, 733596141U, 267099868U, 15311432U};
constexpr unsigned INV_FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 86583718U, 509520358U, 337190230U, 87557064U, 609441965U, 135236158U, 304459705U, 685443576U, 381598368U, 335559352U, 129292727U, 358024708U, 814576206U, 708402881U, 283043518U, 3707709U, 121392023U, 704923114U, 950391366U, 428961804U, 382752275U, 469870224U};
constexpr unsigned FFT_RATIOS[FFT_MAX] = {911660635U, 509520358U, 369330050U, 332049552U, 983190778U, 123842337U, 238493703U, 975955924U, 603855026U, 856644456U, 131300601U, 842657263U, 730768835U, 942482514U, 806263778U, 151565301U, 510815449U, 503497456U, 743006876U, 741047443U, 56250497U, 867605899U};
constexpr unsigned INV_FFT_RATIOS[FFT_MAX] = {86583718U, 372528824U, 373294451U, 645684063U, 112220581U, 692852209U, 155456985U, 797128860U, 90816748U, 860285882U, 927414960U, 354738543U, 109331171U, 293255632U, 535113200U, 308540755U, 121186627U, 608385704U, 438932459U, 359477183U, 824071951U, 103369235U};
} // namespace noya2::internal
struct ntt998244353 {
using mint = modint998244353;
static constexpr unsigned MO = modint998244353::mod();
static constexpr unsigned MO2 = MO * 2;
static void ntt(mint *as, int n){
int m = n;
if (m >>= 1){
for (int i = 0; i < m; i++){
const unsigned x = as[i + m]._v;
as[i + m]._v = as[i]._v + MO - x;
as[i]._v += x;
}
}
if (m >>= 1){
mint prod = 1;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
for (int i = i0; i < i0 + m; i++){
const unsigned x = (prod * as[i + m])._v;
as[i + m]._v = as[i]._v + MO - x;
as[i]._v += x;
}
prod *= mint::raw(internal::FFT_RATIOS[__builtin_ctz(++h)]);
}
}
for (; m; ){
if (m >>= 1){
mint prod = 1;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
for (int i = i0; i < i0 + m; i++){
const unsigned x = (prod * as[i + m])._v;
as[i + m]._v = as[i]._v + MO - x;
as[i]._v += x;
}
prod *= mint::raw(internal::FFT_RATIOS[__builtin_ctz(++h)]);
}
}
if (m >>= 1){
mint prod = 1;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
for (int i = i0; i < i0 + m; i++){
const unsigned x = (prod * as[i + m])._v;
as[i]._v = (as[i]._v >= MO2 ? as[i]._v - MO2 : as[i]._v);
as[i + m]._v = as[i]._v + MO - x;
as[i]._v += x;
}
prod *= mint::raw(internal::FFT_RATIOS[__builtin_ctz(++h)]);
}
}
}
for (int i = 0; i < n; i++){
as[i]._v = (as[i]._v >= MO2 ? as[i]._v - MO2 : as[i]._v);
as[i]._v = (as[i]._v >= MO ? as[i]._v - MO : as[i]._v);
}
}
static void intt(mint *as, int n){
int m = 1;
if (m < (n >> 1)){
mint prod = 1;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
for (int i = i0; i < i0 + m; i++){
const unsigned long long y = as[i]._v + MO - as[i + m]._v;
as[i]._v += as[i + m]._v;
as[i + m]._v = prod._v * y % MO;
}
prod *= mint::raw(internal::INV_FFT_RATIOS[__builtin_ctz(++h)]);
}
m <<= 1;
}
for (; m < (n >> 1); m <<= 1){
mint prod = 1;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
for (int i = i0; i < i0 + (m >> 1); i++){
const unsigned long long y = as[i]._v + MO2 - as[i + m]._v;
as[i]._v += as[i + m]._v;
as[i]._v = (as[i]._v >= MO2 ? as[i]._v - MO2 : as[i]._v);
as[i + m]._v = prod._v * y % MO;
}
for (int i = i0 + (m >> 1); i < i0 + m; i++){
const unsigned long long y = as[i]._v + MO - as[i + m]._v;
as[i]._v += as[i + m]._v;
as[i + m]._v = prod._v * y % MO;
}
prod *= mint::raw(internal::INV_FFT_RATIOS[__builtin_ctz(++h)]);
}
}
if (m < n){
for (int i = 0; i < m; i++){
const unsigned y = as[i]._v + MO2 - as[i + m]._v;
as[i]._v += as[i + m]._v;
as[i + m]._v = y;
}
}
for (int i = 0; i < n; i++){
as[i]._v = (as[i]._v >= MO2 ? as[i]._v - MO2 : as[i]._v);
as[i]._v = (as[i]._v >= MO ? as[i]._v - MO : as[i]._v);
}
}
static void ntt(std::vector<mint> &as){
ntt(as.data(), as.size());
}
static void intt(std::vector<mint> &as){
intt(as.data(), as.size());
}
static void intt_div(std::vector<mint> &as){
intt(as);
int n = as.size();
const mint inv_n = mint::raw(n).inv();
for (int i = 0; i < n; i++){
as[i] *= inv_n;
}
}
static std::vector<mint> multiply(std::vector<mint> as, std::vector<mint> bs){
if (as.empty() || bs.empty()) return {};
const int len = as.size() + bs.size() - 1u;
if (std::min(as.size(), bs.size()) <= 40u){
std::vector<mint> s(len);
for (int i = 0; i < (int)(as.size()); i++){
for (int j = 0; j < (int)(bs.size()); j++){
s[i + j] += as[i] * bs[j];
}
}
return s;
}
int n = 1;
for (; n < len; n <<= 1) {}
if (as.size() == bs.size() && as == bs){
as.resize(n);
ntt(as);
for (int i = 0; i < n; i++){
as[i] *= as[i];
}
}
else {
as.resize(n);
ntt(as);
bs.resize(n);
ntt(bs);
for (int i = 0; i < n; i++){
as[i] *= bs[i];
}
}
intt_div(as);
as.resize(len);
return as;
}
static void ntt_doubling(std::vector<mint> &as){
auto bs = as;
intt(bs);
mint e = mint::raw(internal::FFT_ROOTS[std::countr_zero(as.size()) + 1]);
mint iv = mint::raw(as.size()).inv();
for (auto &x : bs){
x *= iv;
iv *= e;
}
ntt(bs);
as.insert(as.end(), bs.begin(), bs.end());
}
static void ntt_pick_parity(std::vector<mint> &f, int odd){
int n = f.size() / 2;
mint i2 = mint::raw((mint::mod() + 1) >> 1);
if (odd == 0){
for (int i = 0; i < n; i++){
f[i] = (f[i * 2] + f[i * 2 + 1]) * i2;
}
f.resize(n);
return ;
}
mint ie = mint::raw(internal::INV_FFT_ROOTS[std::countr_zero(f.size())]);
std::vector<mint> es = {i2};
while ((int)(es.size()) != n){
std::vector<mint> nes(es.size() * 2u);
for (int i = 0; i < (int)(es.size()); i++){
nes[i * 2 + 0] = es[i];
nes[i * 2 + 1] = es[i] * ie;
}
ie *= ie;
std::swap(es, nes);
}
for (int i = 0; i < n; i++){
f[i] = (f[i * 2] - f[i * 2 + 1]) * es[i];
}
f.resize(n);
}
};
} // namespace noya2
#line 7 "/Users/noya2/Desktop/Noya2_library/fps998244353/fps998244353.hpp"
namespace noya2 {
// Formal Power Series for modint998244353
struct fps998244353 : std::vector<modint998244353> {
using mint = modint998244353;
using std::vector<mint>::vector;
using std::vector<mint>::operator=;
using fps = fps998244353;
static inline binomial<mint> bnm;
fps998244353 (const std::vector<mint> &init){
(*this) = init;
}
void shrink(){
while(!(this->empty()) && this->back().val() == 0){
this->pop_back();
}
}
fps &operator*= (const mint &r){
for (auto &x : *this) x *= r;
return *this;
}
fps &operator/= (const mint &r){
(*this) *= r.inv();
return *this;
}
fps &operator<<= (const int &d){
this->insert(this->begin(), d, mint(0));
return *this;
}
fps &operator>>= (const int &d){
if ((int)(this->size()) <= d) this->clear();
else this->erase(this->begin(),this->begin() + d);
return *this;
}
fps &operator+= (const fps &r){
if (this->size() < r.size()) this->resize(r.size());
for (int i = 0; auto x : r){
(*this)[i++] += x;
}
return *this;
}
fps &operator-= (const fps &r){
if (this->size() < r.size()) this->resize(r.size());
for (int i = 0; auto x : r){
(*this)[i++] -= x;
}
return *this;
}
fps &operator*= (const fps &r){
if (this->empty() || r.empty()){
this->clear();
return *this;
}
(*this) = ntt998244353::multiply(*this, r);
return *this;
}
fps operator* (const mint &r) const { return fps(*this) *= r; }
fps operator/ (const mint &r) const { return fps(*this) /= r; }
fps operator<< (const int &d) const { return fps(*this) <<= d; }
fps operator>> (const int &d) const { return fps(*this) >>= d; }
fps operator+ (const fps &r) const { return fps(*this) += r; }
fps operator- (const fps &r) const { return fps(*this) -= r; }
fps operator* (const fps &r) const { return fps(*this) *= r; }
fps operator+ () const { return *this; }
fps operator- () const {
fps ret(*this);
for (auto &x : ret) x = -x;
return ret;
}
mint eval(const mint &x) const {
mint res(0), w(1);
for (auto a : *this){
res += a * w;
w *= x;
}
return res;
}
[[nodiscard("Do not change but return changed object.")]]
fps pre(std::size_t sz) const {
fps ret(this->begin(), this->begin() + std::min(this->size(), sz));
if (ret.size() < sz) ret.resize(sz);
return ret;
}
[[nodiscard("Do not change but return changed object.")]]
fps rev() const {
fps ret(*this);
std::reverse(ret.begin(), ret.end());
return ret;
}
[[nodiscard("Do not change but return changed object.")]]
fps diff() const {
if (this->empty()){
return fps();
}
fps ret(this->begin() + 1, this->end());
for (int i = 1; auto &x : ret){
x *= i++;
}
return ret;
}
[[nodiscard("Do not change but return changed object.")]]
fps integral() const {
if (this->empty()){
return fps();
}
fps ret(1, mint(0));
ret.insert(ret.end(), this->begin(), this->end());
for (int i = 0; auto &x : ret){
x *= bnm.inv(i++); // inv(0) = 0
}
return ret;
}
[[nodiscard("Do not change but return changed object.")]]
fps inv(int d = -1) const {
const int n = this->size();
if (d == -1) d = n;
fps res = {(*this)[0].inv()};
for (int siz = 1; siz < d; siz <<= 1){
fps f(this->begin(),this->begin()+min(n,siz*2)), g(res);
f.resize(siz*2), g.resize(siz*2);
f.ntt(), g.ntt();
for (int i = 0; i < siz*2; i++) f[i] *= g[i];
f.intt();
f.erase(f.begin(),f.begin()+siz);
f.resize(siz*2);
f.ntt();
for (int i = 0; i < siz*2; i++) f[i] *= g[i];
f.intt();
mint siz2_inv = mint(siz*2).inv(); siz2_inv *= -siz2_inv;
for (int i = 0; i < siz; i++) f[i] *= siz2_inv;
res.insert(res.end(),f.begin(),f.begin()+siz);
}
res.resize(d);
return res;
}
[[nodiscard("Do not change but return changed object.")]]
fps log(int d = -1) const {
assert(this->empty() == false && (*this)[0].val() == 1u);
if (d == -1) d = this->size();
return (this->diff() * this->inv(d)).pre(d - 1).integral();
}
[[nodiscard("Do not change but return changed object.")]]
fps exp(int d = -1) const {
const int n = this->size();
if (d == -1) d = n;
assert(n == 0 || (*this)[0].val() == 0u);
if (n <= 1){
fps ret(1,1);
ret.resize(d);
return ret;
}
// n >= 2
fps f = {mint(1), (*this)[1]}, ret = f;
for (int sz = 2; sz < d; sz <<= 1){
f.insert(f.end(), this->begin()+std::min(n,sz), this->begin()+std::min(n,sz*2));
f.resize(sz*2);
ret *= f - ret.log(sz*2);
ret.resize(sz*2);
}
ret.resize(d);
return ret;
}
[[nodiscard("Do not change but return changed object.")]]
fps pow(long long k, int d = -1) const {
const int n = this->size();
if (d == -1) d = n;
if (k == 0){
fps ret(d, mint(0));
if (d >= 1) ret[0] = 1;
return ret;
}
// Find left-most nonzero term.
for (int i = 0; i < n; i++){
if ((*this)[i].val() != 0u){
mint iv = (*this)[i].inv();
fps ret = ((((*this) * iv) >> i).log(d) * mint(k)).exp(d);
ret *= (*this)[i].pow(k);
ret = (ret << (i * k)).pre(d);
return ret;
}
if ((i + 1) * k >= d) break;
}
return fps(d, mint(0));
}
void ntt(){
ntt998244353::ntt(*this);
}
// NOT /= len
void intt(){
ntt998244353::intt(*this);
}
// already /= len
void intt_div(){
ntt998244353::intt_div(*this);
}
// input : ntt( f[0, 2^n) )
// output : ntt( f[0, 2^n) ++ zero_padding[0, 2^n) )
void ntt_doubling(){
ntt998244353::ntt_doubling(*this);
}
// input : ntt( f[0, 2^n) )
// output : ntt( g[0, 2^{n-1}) ), g[i] = f[i * 2 + odd]
void ntt_pick_parity(int odd){
ntt998244353::ntt_pick_parity(*this, odd);
}
fps quotient(fps r) const {
r.shrink();
const int n = this->size(), m = r.size();
if (n < m){
return fps();
}
fps quo(*this);
const int sz = n - m + 1;
std::reverse(quo.begin(), quo.end());
std::reverse(r.begin(), r.end());
quo.resize(sz);
quo *= r.inv(sz);
quo.resize(sz);
std::reverse(quo.begin(), quo.end());
return quo;
}
fps remainder(fps r) const {
r.shrink();
const int n = this->size(), m = r.size();
if (n < m){
return fps(*this);
}
fps rem(*this);
rem -= quotient(r) * r;
rem.resize(m-1);
rem.shrink();
return rem;
}
std::pair<fps,fps> remquo(fps r) const {
r.shrink();
fps quo = quotient(r);
fps rem(*this);
rem -= quo * r;
rem.shrink();
return {rem, quo};
}
};
} // namespace noya2
#line 8 "c.cpp"
using fps = fps998244353;
#line 2 "/Users/noya2/Desktop/Noya2_library/fps998244353/multipoint_evaluation.hpp"
#line 4 "/Users/noya2/Desktop/Noya2_library/fps998244353/multipoint_evaluation.hpp"
namespace noya2 {
std::vector<modint998244353> multipoint_evaluation(fps998244353 f, const std::vector<modint998244353> &xs){
const int n = xs.size();
int sz = 1;
while(sz < n) sz <<= 1;
std::vector<fps998244353> g(sz+sz,{1});
for(int i = 0; i < n; i++) g[i+sz] = {-xs[i],1};
for(int i = sz; i-->1;) g[i] = g[i<<1] * g[i<<1|1];
g[1] = f.remainder(g[1]);
for(int i = 2; i < sz+n; i++) g[i] = g[i>>1].remainder(g[i]);
std::vector<modint998244353> res(n);
for(int i = 0; i < n; i++) res[i] = (g[i+sz].empty() ? modint998244353() : g[i+sz][0]);
return res;
}
std::vector<modint998244353> multipoint_evaluation_geo(const fps998244353 &f, modint998244353 a, modint998244353 r, int m){
using mint = modint998244353;
int n = f.size();
if (r.val() == 0){
std::vector<mint> ans(m);
repp(i,1,m) ans[i] = f[0];
ans[0] = f.eval(a);
return ans;
}
fps998244353 p(n);
mint aprd = 1;
mint ir = r.inv();
mint irpp = 1, irp = 1;
for (int i = 0; i < n; i++){
p[n-1-i] = aprd * f[i] * irpp;
irpp *= irp;
irp *= ir;
aprd *= a;
}
fps998244353 q(n+m-1);
mint rpp = 1, rp = 1;
for (int i = 0; i < n+m-1; i++){
q[i] = rpp;
rpp *= rp;
rp *= r;
}
p *= q;
std::vector<mint> ans(m);
irpp = 1, irp = 1;
for (int i = 0; i < m; i++){
ans[i] = p[n-1+i] * irpp;
irpp *= irp;
irp *= ir;
}
return ans;
}
} // namespace noya2
#line 10 "c.cpp"
// [x^n](1/(1-x))^k
mint h(int n, int k){
if (k == 0){
return int(n == 0);
}
return bnm(n+k-1,k-1);
}
// [x^n](exp(x))^k
mint h2(int n, int k){
// return fps{0,k}.exp(n+1)[n];
return mint(k).pow(n) * bnm.ifact(n);
}
void jikken1(){
int n; in(n);
mint ans = 0;
repp(k,1,n+1) rep(p,n+1){
mint sum = 0;
rep(i,k+1){
sum += bnm(k,i) * h2(p,i) * (i % 2 == 0 ? 1 : -1) * h2(n-p,n-i);
}
ans += sum * mint(n-p).pow(n);
}
ans *= bnm.fact(n);
out(ans);
}
void jikken2(){
int n; in(n);
mint ans = 0;
rep(p,n+1) rep(i,n+1){
ans += mint(n-p).pow(n) * (i % 2 == 0 ? 1 : -1) * h2(p,i) * h2(n-p,n-i) * bnm(n+1,i+1);
}
ans *= bnm.fact(n);
ans -= mint(n).pow(n*2);
out(ans);
}
namespace Forested {
#ifndef LOCAL
#define FAST_IO
#endif
#define INT128
// ============
#line 59 "c.cpp"
#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, m, n) for (i32 i = (i32)(n)-1; i >= (i32)(m); --i)
#define PER(...) OVERRIDE(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define LEN(x) (i32)(x.size())
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;
using pi = pair<i32, i32>;
using pl = pair<i64, i64>;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<V<V<T>>>;
template <typename T>
using VVVV = V<V<V<V<T>>>>;
template <typename T>
using PQR = priority_queue<T, V<T>, greater<T>>;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <typename T>
i32 lob(const V<T> &arr, const T &v) {
return (i32)(lower_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
i32 upb(const V<T> &arr, const T &v) {
return (i32)(upper_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
V<i32> argsort(const V<T> &arr) {
V<i32> ret(arr.size());
iota(ALL(ret), 0);
sort(ALL(ret), [&](i32 i, i32 j) -> bool {
if (arr[i] == arr[j]) {
return i < j;
} else {
return arr[i] < arr[j];
}
});
return ret;
}
#ifdef INT128
using u128 = __uint128_t;
using i128 = __int128_t;
#endif
[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
SetUpIO() {
#ifdef FAST_IO
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cout << fixed << setprecision(15);
}
} set_up_io;
void scan(char &x) { cin >> x; }
void scan(u32 &x) { cin >> x; }
void scan(u64 &x) { cin >> x; }
void scan(i32 &x) { cin >> x; }
void scan(i64 &x) { cin >> x; }
void scan(f64 &x) { cin >> x; }
void scan(string &x) { cin >> x; }
template <typename T>
void scan(V<T> &x) {
for (T &ele : x) {
scan(ele);
}
}
void read() {}
template <typename Head, typename... Tail>
void read(Head &head, Tail &...tail) {
scan(head);
read(tail...);
}
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__);
#define U32(...) \
u32 __VA_ARGS__; \
read(__VA_ARGS__);
#define U64(...) \
u64 __VA_ARGS__; \
read(__VA_ARGS__);
#define I32(...) \
i32 __VA_ARGS__; \
read(__VA_ARGS__);
#define I64(...) \
i64 __VA_ARGS__; \
read(__VA_ARGS__);
#define F64(...) \
f64 __VA_ARGS__; \
read(__VA_ARGS__);
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__);
#define VEC(type, name, size) \
V<type> name(size); \
read(name);
#define VVEC(type, name, size1, size2) \
VV<type> name(size1, V<type>(size2)); \
read(name);
// ============
#ifdef DEBUGF
#else
#define DBG(...) (void)0
#endif
// ============
#line 194 "c.cpp"
// ============
#line 197 "c.cpp"
// ============
#line 201 "c.cpp"
#include <type_traits>
// ============
#line 205 "c.cpp"
constexpr bool is_prime(unsigned n) {
if (n == 0 || n == 1) {
return false;
}
for (unsigned i = 2; i * i <= n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
constexpr unsigned mod_pow(unsigned x, unsigned y, unsigned mod) {
unsigned ret = 1, self = x;
while (y != 0) {
if (y & 1) {
ret = (unsigned)((unsigned long long)ret * self % mod);
}
self = (unsigned)((unsigned long long)self * self % mod);
y /= 2;
}
return ret;
}
template <unsigned mod>
constexpr unsigned primitive_root() {
static_assert(is_prime(mod), "`mod` must be a prime number.");
if (mod == 2) {
return 1;
}
unsigned primes[32] = {};
int it = 0;
{
unsigned m = mod - 1;
for (unsigned i = 2; i * i <= m; ++i) {
if (m % i == 0) {
primes[it++] = i;
while (m % i == 0) {
m /= i;
}
}
}
if (m != 1) {
primes[it++] = m;
}
}
for (unsigned i = 2; i < mod; ++i) {
bool ok = true;
for (int j = 0; j < it; ++j) {
if (mod_pow(i, (mod - 1) / primes[j], mod) == 1) {
ok = false;
break;
}
}
if (ok) return i;
}
return 0;
}
// y >= 1
template <typename T>
constexpr T safe_mod(T x, T y) {
x %= y;
if (x < 0) {
x += y;
}
return x;
}
// y != 0
template <typename T>
constexpr T floor_div(T x, T y) {
if (y < 0) {
x *= -1;
y *= -1;
}
if (x >= 0) {
return x / y;
} else {
return -((-x + y - 1) / y);
}
}
// y != 0
template <typename T>
constexpr T ceil_div(T x, T y) {
if (y < 0) {
x *= -1;
y *= -1;
}
if (x >= 0) {
return (x + y - 1) / y;
} else {
return -(-x / y);
}
}
// b >= 1
// returns (g, x) s.t. g = gcd(a, b), a * x = g (mod b), 0 <= x < b / g
// from ACL
template <typename T>
std::pair<T, T> extgcd(T a, T b) {
a = safe_mod(a, b);
T s = b, t = a, m0 = 0, m1 = 1;
while (t) {
T u = s / t;
s -= t * u;
m0 -= m1 * u;
std::swap(s, t);
std::swap(m0, m1);
}
if (m0 < 0) {
m0 += b / s;
}
return std::pair<T, T>(s, m0);
}
// b >= 1
// returns (g, x, y) s.t. g = gcd(a, b), a * x + b * y = g, 0 <= x < b / g, |y| < max(2, |a| / g)
template <typename T>
std::tuple<T, T, T> extgcd2(T a, T b) {
T _a = safe_mod(a, b);
T quot = (a - _a) / b;
T x00 = 0, x01 = 1, y0 = b;
T x10 = 1, x11 = -quot, y1 = _a;
while (y1) {
T u = y0 / y1;
x00 -= u * x10;
x01 -= u * x11;
y0 -= u * y1;
std::swap(x00, x10);
std::swap(x01, x11);
std::swap(y0, y1);
}
if (x00 < 0) {
x00 += b / y0;
x01 -= a / y0;
}
return std::tuple<T, T, T>(y0, x00, x01);
}
// gcd(x, m) == 1
template <typename T>
T inv_mod(T x, T m) {
return extgcd(x, m).second;
}
// ============
template <unsigned mod>
struct ModInt {
static_assert(mod != 0, "`mod` must not be equal to 0.");
static_assert(mod < (1u << 31),
"`mod` must be less than (1u << 31) = 2147483648.");
unsigned val;
static constexpr unsigned get_mod() { return mod; }
constexpr ModInt() : val(0) {}
template <typename T, std::enable_if_t<std::is_signed_v<T>> * = nullptr>
constexpr ModInt(T x)
: val((unsigned)((long long)x % (long long)mod + (x < 0 ? mod : 0))) {}
template <typename T, std::enable_if_t<std::is_unsigned_v<T>> * = nullptr>
constexpr ModInt(T x) : val((unsigned)(x % mod)) {}
static constexpr ModInt raw(unsigned x) {
ModInt<mod> ret;
ret.val = x;
return ret;
}
constexpr unsigned get_val() const { return val; }
constexpr ModInt operator+() const { return *this; }
constexpr ModInt operator-() const { return ModInt<mod>(0u) - *this; }
constexpr ModInt &operator+=(const ModInt &rhs) {
val += rhs.val;
if (val >= mod) val -= mod;
return *this;
}
constexpr ModInt &operator-=(const ModInt &rhs) {
val -= rhs.val;
if (val >= mod) val += mod;
return *this;
}
constexpr ModInt &operator*=(const ModInt &rhs) {
val = (unsigned long long)val * rhs.val % mod;
return *this;
}
constexpr ModInt &operator/=(const ModInt &rhs) {
val = (unsigned long long)val * rhs.inv().val % mod;
return *this;
}
friend constexpr ModInt operator+(const ModInt &lhs, const ModInt &rhs) {
return ModInt<mod>(lhs) += rhs;
}
friend constexpr ModInt operator-(const ModInt &lhs, const ModInt &rhs) {
return ModInt<mod>(lhs) -= rhs;
}
friend constexpr ModInt operator*(const ModInt &lhs, const ModInt &rhs) {
return ModInt<mod>(lhs) *= rhs;
}
friend constexpr ModInt operator/(const ModInt &lhs, const ModInt &rhs) {
return ModInt<mod>(lhs) /= rhs;
}
constexpr ModInt pow(unsigned long long x) const {
ModInt<mod> ret = ModInt<mod>::raw(1);
ModInt<mod> self = *this;
while (x != 0) {
if (x & 1) ret *= self;
self *= self;
x >>= 1;
}
return ret;
}
constexpr ModInt inv() const {
static_assert(is_prime(mod), "`mod` must be a prime number.");
assert(val != 0);
return this->pow(mod - 2);
}
friend std::istream &operator>>(std::istream &is, ModInt<mod> &x) {
long long val;
is >> val;
x.val = val % mod + (val < 0 ? mod : 0);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &x) {
os << x.val;
return os;
}
friend bool operator==(const ModInt &lhs, const ModInt &rhs) {
return lhs.val == rhs.val;
}
friend bool operator!=(const ModInt &lhs, const ModInt &rhs) {
return lhs.val != rhs.val;
}
};
template <unsigned mod>
void debug(ModInt<mod> x) {
std::cerr << x.val;
}
// ============
constexpr int ctz_constexpr(unsigned n) {
int x = 0;
while (!(n & (1u << x))) {
++x;
}
return x;
}
template <unsigned MOD>
struct FFTRoot {
static constexpr unsigned R = ctz_constexpr(MOD - 1);
std::array<ModInt<MOD>, R + 1> root, iroot;
std::array<ModInt<MOD>, R> rate2, irate2;
std::array<ModInt<MOD>, R - 1> rate3, irate3;
std::array<ModInt<MOD>, R + 1> inv2;
constexpr FFTRoot() : root{}, iroot{}, rate2{}, irate2{}, rate3{}, irate3{}, inv2{} {
unsigned pr = primitive_root<MOD>();
root[R] = ModInt<MOD>(pr).pow(MOD >> R);
iroot[R] = root[R].inv();
for (int i = R - 1; i >= 0; --i) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
ModInt<MOD> prod(1), iprod(1);
for (int i = 0; i < (int)R - 1; ++i) {
rate2[i] = prod * root[i + 2];
irate2[i] = iprod * iroot[i + 2];
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
prod = ModInt<MOD>(1);
iprod = ModInt<MOD>(1);
for (int i = 0; i < (int)R - 2; ++i) {
rate3[i] = prod * root[i + 3];
irate3[i] = iprod * iroot[i + 3];
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
ModInt<MOD> i2 = ModInt<MOD>(2).inv();
inv2[0] = ModInt<MOD>(1);
for (int i = 0; i < (int)R; ++i) {
inv2[i + 1] = inv2[i] * i2;
}
}
};
template <typename M>
void fft(M *a, int n) {
using ull = unsigned long long;
static_assert(M::get_mod() < (1u << 30));
static constexpr FFTRoot<M::get_mod()> fftroot;
static constexpr ull CEIL = 2ULL * M::get_mod() * M::get_mod();
int l = __builtin_ctz(n);
int ph = 0;
while (ph < l) {
if (ph + 1 == l) {
int b = 1 << ph;
M z = M::raw(1);
for (int i = 0; i < b; ++i) {
int offset = i << 1;
M x = a[offset];
M y = a[offset + 1] * z;
a[offset] = x + y;
a[offset + 1] = x - y;
z *= fftroot.rate2[__builtin_ctz(~i)];
}
++ph;
} else {
int bl = 1 << ph;
int wd = 1 << (l - 2 - ph);
M zeta = M::raw(1);
for (int i = 0; i < bl; ++i) {
int offset = i << (l - ph);
M zeta2 = zeta * zeta;
M zeta3 = zeta2 * zeta;
for (int j = 0; j < wd; ++j) {
ull w = a[offset + j].val;
ull x = (ull)a[offset + j + wd].val * zeta.val;
ull y = (ull)a[offset + j + 2 * wd].val * zeta2.val;
ull z = (ull)a[offset + j + 3 * wd].val * zeta3.val;
ull ix_m_iz = (CEIL + x - z) % M::get_mod() * fftroot.root[2].val;
a[offset + j] = M(w + x + y + z);
a[offset + j + wd] = M(CEIL + w - x + y - z);
a[offset + j + 2 * wd] = M(CEIL + w - y + ix_m_iz);
a[offset + j + 3 * wd] = M(CEIL + w - y - ix_m_iz);
}
zeta *= fftroot.rate3[__builtin_ctz(~i)];
}
ph += 2;
}
}
}
template <typename M>
void ifft(M *a, int n) {
using ull = unsigned long long;
static_assert(M::get_mod() < (1u << 30));
static constexpr FFTRoot<M::get_mod()> fftroot;
int l = __builtin_ctz(n);
int ph = l;
while (ph > 0) {
if (ph == 1) {
--ph;
int wd = 1 << (l - 1);
for (int i = 0; i < wd; ++i) {
M x = a[i];
M y = a[i + wd];
a[i] = x + y;
a[i + wd] = x - y;
}
} else {
ph -= 2;
int bl = 1 << ph;
int wd = 1 << (l - 2 - ph);
M zeta = M::raw(1);
for (int i = 0; i < bl; ++i) {
int offset = i << (l - ph);
M zeta2 = zeta * zeta;
M zeta3 = zeta2 * zeta;
for (int j = 0; j < wd; ++j) {
unsigned w = a[offset + j].val;
unsigned x = a[offset + j + wd].val;
unsigned y = a[offset + j + 2 * wd].val;
unsigned z = a[offset + j + 3 * wd].val;
unsigned iy_m_iz = (ull)(M::get_mod() + y - z) * fftroot.root[2].val % M::get_mod();
a[offset + j] = M(w + x + y + z);
a[offset + j + wd] = M((ull)zeta.val * (2 * M::get_mod() + w - x - iy_m_iz));
a[offset + j + 2 * wd] = M((ull)zeta2.val * (2 * M::get_mod() + w + x - y - z));
a[offset + j + 3 * wd] = M((ull)zeta3.val * (M::get_mod() + w - x + iy_m_iz));
}
zeta *= fftroot.irate3[__builtin_ctz(~i)];
}
}
}
for (int i = 0; i < n; ++i) {
a[i] *= fftroot.inv2[l];
}
}
template <typename M>
void fft(std::vector<M> &a) {
fft(a.data(), (int)a.size());
}
template <typename M>
void ifft(std::vector<M> &a) {
ifft(a.data(), (int)a.size());
}
template <typename M>
std::vector<M> convolve_naive(const std::vector<M> &a,
const std::vector<M> &b) {
int n = (int)a.size();
int m = (int)b.size();
std::vector<M> c(n + m - 1);
if (n < m) {
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
c[i + j] += a[i] * b[j];
}
}
} else {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
c[i + j] += a[i] * b[j];
}
}
}
return c;
}
template <typename M>
std::vector<M> convolve_fft(std::vector<M> a, std::vector<M> b) {
int n = (int)a.size() + (int)b.size() - 1;
int m = 1;
while (m < n) {
m <<= 1;
}
bool shr = false;
M last;
if (n >= 3 && n == m / 2 + 1) {
shr = true;
last = a.back() * b.back();
m /= 2;
while ((int)a.size() > m) {
a[(int)a.size() - 1 - m] += a.back();
a.pop_back();
}
while ((int)b.size() > m) {
b[(int)b.size() - 1 - m] += b.back();
b.pop_back();
}
}
a.resize(m);
b.resize(m);
fft(a);
fft(b);
for (int i = 0; i < m; ++i) {
a[i] *= b[i];
}
ifft(a);
a.resize(n);
if (shr) {
a[0] -= last;
a[n - 1] = last;
}
return a;
}
template <typename M>
std::vector<M> convolve(const std::vector<M> &a, const std::vector<M> &b) {
if (a.empty() || b.empty()) {
return std::vector<M>(0);
}
if (std::min(a.size(), b.size()) <= 60) {
return convolve_naive(a, b);
} else {
return convolve_fft(a, b);
}
}
template <typename M>
std::vector<M> convolve_square_fft(std::vector<M> a) {
int n = (int)2 * a.size() - 1;
int m = 1;
while (m < n) {
m <<= 1;
}
bool shr = false;
M last;
if (n >= 3 && n == m / 2 + 1) {
shr = true;
last = a.back() * a.back();
m /= 2;
while ((int)a.size() > m) {
a[(int)a.size() - 1 - m] += a.back();
a.pop_back();
}
}
a.resize(m);
fft(a);
for (int i = 0; i < m; ++i) {
a[i] *= a[i];
}
ifft(a);
a.resize(n);
if (shr) {
a[0] -= last;
a[n - 1] = last;
}
return a;
}
template <typename M>
std::vector<M> convolve_square(const std::vector<M> &a) {
if (a.empty()) {
return std::vector<M>(0);
}
if ((int)a.size() <= 60) {
return convolve_naive(a, a);
} else {
return convolve_square_fft(a);
}
}
template <typename M>
void transposed_fft(M *a, int n) {
ifft(a, n);
std::reverse(a + 1, a + n);
M c(n);
for (int i = 0; i < n; ++i) {
a[i] *= c;
}
}
template <typename M>
void transposed_fft(std::vector<M> &a) {
transposed_fft(a.data(), (int)a.size());
}
template <typename M>
void transposed_ifft(M *a, int n) {
static constexpr FFTRoot<M::get_mod()> roots;
std::reverse(a + 1, a + n);
fft(a, n);
M c = roots.inv2[__builtin_ctz(n)];
for (int i = 0; i < n; ++i) {
a[i] *= c;
}
}
template <typename M>
void transposed_ifft(std::vector<M> &a) {
transposed_ifft(a.data(), (int)a.size());
}
// ============
// 10 FFT(n)
template <typename T>
std::vector<T> fps_inv(const std::vector<T> &f, int len = -1) {
if (len == -1) {
len = (int)f.size();
}
assert(!f.empty() && f[0] != T(0) && len >= 0);
std::vector<T> g(1, T(1) / f[0]);
while ((int)g.size() < len) {
int n = (int)g.size();
std::vector<T> fft_f(2 * n), fft_g(2 * n);
std::copy(f.begin(), f.begin() + std::min(2 * n, (int)f.size()),
fft_f.begin());
std::copy(g.begin(), g.end(), fft_g.begin());
fft(fft_f);
fft(fft_g);
for (int i = 0; i < 2 * n; ++i) {
fft_f[i] *= fft_g[i];
}
ifft(fft_f);
std::fill(fft_f.begin(), fft_f.begin() + n, T(0));
fft(fft_f);
for (int i = 0; i < 2 * n; ++i) {
fft_f[i] *= fft_g[i];
}
ifft(fft_f);
g.resize(2 * n);
for (int i = n; i < 2 * n; ++i) {
g[i] = -fft_f[i];
}
}
g.resize(len);
return g;
}
// ============
// ============
#line 790 "c.cpp"
// ============
// ============
// a.size() <= b.size()
template <typename M>
std::vector<M> middle_product(std::vector<M> a, std::vector<M> b) {
int n = (int)a.size();
int m = (int)b.size();
assert(n <= m);
std::reverse(a.begin(), a.end());
int l = 1;
while (l < m) {
l *= 2;
}
a.resize(l, M());
b.resize(l, M());
fft(a);
fft(b);
for (int i = 0; i < l; ++i) {
b[i] *= a[i];
}
ifft(b);
return std::vector<M>(b.begin() + (n - 1), b.begin() + m);
}
// ============
i32 ceil_log2(i32 n) {
i32 k = 0;
while ((1 << k) < n) {
++k;
}
return k;
}
using M = ModInt<998244353>;
V<M> sum_inv(const V<M> &a, const V<M> &b, i32 m) {
static constexpr FFTRoot<M::get_mod()> root{};
assert(LEN(a) == LEN(b));
const i32 old = LEN(a);
const i32 lg = ceil_log2(LEN(a));
const i32 n = 1 << lg;
const i32 n2 = n * 2;
V<M> c(n2), d(n2);
REP(i, old) {
c[2 * i] = c[2 * i + 1] = a[i];
d[2 * i] = M(1) - b[i];
d[2 * i + 1] = M(1) + b[i];
}
fill(begin(d) + 2 * old, end(d), M(1));
REP(ph, lg) {
const i32 w = 1 << (ph + 1), w2 = w * 2;
M omega = root.root[ph + 2];
for (i32 i = 0; i < n2; i += w2) {
const i32 ti = i + w;
REP(j, w) {
c[ti + j] = c[i + j] = c[i + j] * d[ti + j] + c[ti + j] * d[i + j];
d[ti + j] = d[i + j] *= d[ti + j];
}
ifft(c.data() + ti, w);
ifft(d.data() + ti, w);
d[ti] = M(2) - d[ti];
M pw(1);
REP(j, w) {
c[ti + j] *= pw;
d[ti + j] *= pw;
pw *= omega;
}
fft(c.data() + ti, w);
fft(d.data() + ti, w);
}
}
ifft(c);
ifft(d);
c.resize(m);
d = fps_inv(d, m);
V<M> ans = convolve(c, d);
ans.resize(m);
return ans;
}
V<M> multieval(V<M> f, const V<M> &p) {
static constexpr FFTRoot<M::get_mod()> root{};
const i32 m = LEN(f);
const i32 _n = LEN(p);
const i32 lg = ceil_log2(_n);
const i32 n = 1 << lg;
const i32 n2 = n * 2;
VV<M> tree(lg + 1, V<M>(n2));
REP(i, _n) {
tree[0][2 * i] = M(1) - p[i];
tree[0][2 * i + 1] = M(1) + p[i];
}
fill(begin(tree[0]) + 2 * _n, end(tree[0]), M(1));
REP(ph, lg) {
const i32 w = 1 << (ph + 1), w2 = w * 2;
M omega = root.root[ph + 2];
V<M> &d = tree[ph + 1];
d = tree[ph];
for (i32 i = 0; i < n2; i += w2) {
const i32 ti = i + w;
REP(j, w) {
d[ti + j] = d[i + j] *= d[ti + j];
}
ifft(d.data() + ti, w);
d[ti] = M(2) - d[ti];
M pw(1);
REP(j, w) {
d[ti + j] *= pw;
pw *= omega;
}
fft(d.data() + ti, w);
}
}
ifft(tree[lg]);
tree[lg] = fps_inv(tree[lg], m);
f.resize(2 * m - 1);
V<M> c = middle_product(tree[lg], f);
c.resize(n2);
transposed_ifft(c);
PER(ph, lg) {
const i32 w = 1 << (ph + 1), w2 = w * 2;
M omega = root.root[ph + 2];
for (i32 i = 0; i < n2; i += w2) {
const i32 ti = i + w;
transposed_fft(c.data() + ti, w);
M pw(1);
REP(j, w) {
c[ti + j] *= pw;
pw *= omega;
}
transposed_ifft(c.data() + ti, w);
REP(j, w) {
M t = c[i + j] + c[ti + j];
c[i + j] = t * tree[ph][ti + j];
c[ti + j] = t * tree[ph][i + j];
}
}
}
V<M> ans(_n);
REP(i, _n) {
ans[i] = c[2 * i] + c[2 * i + 1];
}
return ans;
}
} // namespace Forested
vector<mint> multi(fps f, vector<mint> xs){
int n = f.size(), m = xs.size();
Forested::V<Forested::M> a(n), b(m);
rep(i,n){
a[i] = f[i].val();
}
rep(j,m){
b[j] = xs[j].val();
}
auto ans = Forested::multieval(a, b);
vector<mint> ret(m);
rep(j,m){
ret[j] = ans[j].get_val();
}
return ret;
}
void solve(){
// jikken1();
// jikken2();
int n; in(n);
// assert(n <= 100000); // aaaaaaaaa
fps f(n+1);
rep(p,n+1){
f[n-p] = mint(n-p).pow(n) * bnm.ifact(p) * bnm.ifact(n-p);
}
vector<mint> xs(n);
rep(i,n){
xs[i] = n * bnm.inv(i+1) - 1;
}
// auto ys = multipoint_evaluation(f, xs);
auto ys = multi(f, xs);
mint ans = 0;
// i = 0
rep(p,n+1){
int i = 0;
ans += mint(n-p).pow(n) * (i % 2 == 0 ? 1 : -1) * h2(p,i) * h2(n-p,n-i) * bnm(n+1,i+1);
}
// i = n
// rep(p,n+1){
// int i = n;
// ans += mint(n-p).pow(n) * (i % 2 == 0 ? 1 : -1) * h2(p,i) * h2(n-p,n-i) * bnm(n+1,i+1);
// }
repp(i,1,n+1){
ans += (i % 2 == 0 ? 1 : -1) * bnm(n+1,i+1) * mint(i).pow(n) * ys[i-1];
}
ans *= bnm.fact(n);
ans -= mint(n).pow(n*2);
out(ans);
}
int main(){
int t = 1; //in(t);
while (t--) { solve(); }
}