結果
| 問題 | No.2137 Stairs of Permutation |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2022-11-25 23:30:24 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 22,585 bytes |
| コンパイル時間 | 3,992 ms |
| コンパイル使用メモリ | 310,144 KB |
| 実行使用メモリ | 181,632 KB |
| 最終ジャッジ日時 | 2024-10-02 06:00:08 |
| 合計ジャッジ時間 | 8,228 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
13,640 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 887 ms
44,664 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
ソースコード
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 998244353;
// constexpr int MOD = 1000000007;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << fixed << setprecision(20);
}
} iosetup;
template <int M>
struct MInt {
unsigned int v;
MInt() : v(0) {}
MInt(const long long x) : v(x >= 0 ? x % M : x % M + M) {}
static constexpr int get_mod() { return M; }
static void set_mod(const int divisor) { assert(divisor == M); }
static void init(const int x = 10000000) {
inv(x, true);
fact(x);
fact_inv(x);
}
static MInt inv(const int n, const bool init = false) {
// assert(0 <= n && n < M && std::__gcd(n, M) == 1);
static std::vector<MInt> inverse{0, 1};
const int prev = inverse.size();
if (n < prev) {
return inverse[n];
} else if (init) {
// "n!" and "M" must be disjoint.
inverse.resize(n + 1);
for (int i = prev; i <= n; ++i) {
inverse[i] = -inverse[M % i] * (M / i);
}
return inverse[n];
}
int u = 1, v = 0;
for (unsigned int a = n, b = M; b;) {
const unsigned int q = a / b;
std::swap(a -= q * b, b);
std::swap(u -= q * v, v);
}
return u;
}
static MInt fact(const int n) {
static std::vector<MInt> factorial{1};
const int prev = factorial.size();
if (n >= prev) {
factorial.resize(n + 1);
for (int i = prev; i <= n; ++i) {
factorial[i] = factorial[i - 1] * i;
}
}
return factorial[n];
}
static MInt fact_inv(const int n) {
static std::vector<MInt> f_inv{1};
const int prev = f_inv.size();
if (n >= prev) {
f_inv.resize(n + 1);
f_inv[n] = inv(fact(n).v);
for (int i = n; i > prev; --i) {
f_inv[i - 1] = f_inv[i] * i;
}
}
return f_inv[n];
}
static MInt nCk(const int n, const int k) {
if (n < 0 || n < k || k < 0) return 0;
return fact(n) * (n - k < k ? fact_inv(k) * fact_inv(n - k) :
fact_inv(n - k) * fact_inv(k));
}
static MInt nPk(const int n, const int k) {
return n < 0 || n < k || k < 0 ? 0 : fact(n) * fact_inv(n - k);
}
static MInt nHk(const int n, const int k) {
return n < 0 || k < 0 ? 0 : (k == 0 ? 1 : nCk(n + k - 1, k));
}
static MInt large_nCk(long long n, const int k) {
if (n < 0 || n < k || k < 0) return 0;
inv(k, true);
MInt res = 1;
for (int i = 1; i <= k; ++i) {
res *= inv(i) * n--;
}
return res;
}
MInt pow(long long exponent) const {
MInt res = 1, tmp = *this;
for (; exponent > 0; exponent >>= 1) {
if (exponent & 1) res *= tmp;
tmp *= tmp;
}
return res;
}
MInt& operator+=(const MInt& x) {
if ((v += x.v) >= M) v -= M;
return *this;
}
MInt& operator-=(const MInt& x) {
if ((v += M - x.v) >= M) v -= M;
return *this;
}
MInt& operator*=(const MInt& x) {
v = static_cast<unsigned long long>(v) * x.v % M;
return *this;
}
MInt& operator/=(const MInt& x) { return *this *= inv(x.v); }
bool operator==(const MInt& x) const { return v == x.v; }
bool operator!=(const MInt& x) const { return v != x.v; }
bool operator<(const MInt& x) const { return v < x.v; }
bool operator<=(const MInt& x) const { return v <= x.v; }
bool operator>(const MInt& x) const { return v > x.v; }
bool operator>=(const MInt& x) const { return v >= x.v; }
MInt& operator++() {
if (++v == M) v = 0;
return *this;
}
MInt operator++(int) {
const MInt res = *this;
++*this;
return res;
}
MInt& operator--() {
v = (v == 0 ? M - 1 : v - 1);
return *this;
}
MInt operator--(int) {
const MInt res = *this;
--*this;
return res;
}
MInt operator+() const { return *this; }
MInt operator-() const { return MInt(v ? M - v : 0); }
MInt operator+(const MInt& x) const { return MInt(*this) += x; }
MInt operator-(const MInt& x) const { return MInt(*this) -= x; }
MInt operator*(const MInt& x) const { return MInt(*this) *= x; }
MInt operator/(const MInt& x) const { return MInt(*this) /= x; }
friend std::ostream& operator<<(std::ostream& os, const MInt& x) {
return os << x.v;
}
friend std::istream& operator>>(std::istream& is, MInt& x) {
long long v;
is >> v;
x = MInt(v);
return is;
}
};
using ModInt = MInt<MOD>;
#define cp_lib_4th(_1, _2, _3, x, ...) x
#define cp_lib_rep(i, l, r) for (int i = (l); (i) < (r); ++(i))
#define cp_lib_rep0(i, r) cp_lib_rep(i, 0, r)
#define rep(...) cp_lib_4th(__VA_ARGS__, cp_lib_rep, cp_lib_rep0, _)(__VA_ARGS__)
#define cp_lib_repr(i, r, l, ...) for (int i = (r); (i) >= (l); --(i))
#define repr(...) cp_lib_repr(__VA_ARGS__, 0)
#define all(a) ::begin(a),::end(a)
#define trav(a, b) for (auto&& a : (b))
using namespace std;
using ll = long long;
using ld = long double;
// [[maybe_unused]] static constexpr int INF = int(1e9 + 5);
[[maybe_unused]] static constexpr ll INFL = ll(INF) * INF;
template <class C> int sz(const C& c) { return int(::size(c)); }
#ifdef CP_LIB_DEBUG
#define cp_lib_assert(expr) \
do { if (!(expr)) { \
::cerr << "assertion failed: " << #expr << " (" << __FILE__ << ':' << __LINE__ << ")\n"; \
::abort(); \
} } while (0)
#else
#define cp_lib_assert(expr)
#endif
#if __cplusplus < 202002L
struct identity { template <class T> constexpr T&& operator()(T&& t) const noexcept { return forward<T>(t); }; };
#endif
#if __cpp_lib_remove_cvref < 201711L
template <class T> using remove_cvref_t = remove_cv_t<remove_reference_t<T>>;
#endif
namespace cp_lib_type_meta {
struct NoOp { template <class... Args> constexpr void operator()(Args&&...) const noexcept {} };
template <class T, class = void> constexpr bool is_tuple_like = false;
template <class T> constexpr bool is_tuple_like<T, void_t<tuple_element_t<0, T>>> = true;
}
namespace cp_lib_modint { struct ModIntTag {}; }
#include <unistd.h>
namespace cp_lib_io {
constexpr int BUF_SIZE = 1 << 20;
constexpr array<array<char, 4>, 10'000> DIGITS = []{
array<array<char, 4>, 10'000> digits{};
for (int i = 3, d = 1; i >= 0; --i, d *= 10)
rep(j, 10'000)
digits[j][i] = char('0' + j / d % 10);
return digits;
}();
array<char, BUF_SIZE> ibuf, obuf;
char *iptr = data(ibuf), *iend = iptr, *optr = data(obuf);
template <class T> constexpr bool is_std_array = false;
template <class T, size_t I> constexpr bool is_std_array<array<T, I>> = true;
void flush() {
for (auto* p = begin(obuf); p != optr; p += write(STDOUT_FILENO, p, optr - p));
optr = begin(obuf);
}
int _flush_atexit = []{ atexit(flush); return 0; }();
void refill() {
memmove(begin(ibuf), iptr, iend - iptr);
iend -= iptr - begin(ibuf);
iptr = begin(ibuf);
iend += read(STDIN_FILENO, iend, end(ibuf) - 1 - iend);
*iend = '\0';
}
template <class T, class T2 = remove_cvref_t<T>>
void print(T&& val) {
if (end(obuf) - optr < 64)
flush();
if constexpr (is_same_v<T2, char>)
*optr++ = val;
else if constexpr (is_same_v<T2, bool> || is_same_v<T2, vector<bool>::reference>)
return print(int(val));
else if constexpr (is_integral_v<T2> && is_signed_v<T2>) {
if (val < 0)
*optr++ = '-';
using U = make_unsigned_t<T2>;
return print(U(val < 0 ? -U(val) : U(val)));
} else if constexpr (is_integral_v<T2> && is_unsigned_v<T2>) {
T2 val2 = val;
array<char, 64> tmp;
char* tptr = end(tmp);
while (val2 >= 10'000)
tptr -= 4, memcpy(tptr, &DIGITS[val2 % 10'000][0], 4), val2 /= T2(10'000);
int d = (val2 >= 100 ? (val2 >= 1000 ? 4 : 3) : (val2 >= 10 ? 2 : 1));
memcpy(optr, &DIGITS[val2][4 - d], d);
memcpy(optr + d, tptr, end(tmp) - tptr);
optr += d + int(end(tmp) - tptr);
} else if constexpr (is_floating_point_v<T2>)
optr += sprintf(optr, "%.30Lf", (long double)val);
else if constexpr (is_convertible_v<T, string_view>) {
string_view sv(val);
if (sz(sv) + 1 <= end(obuf) - optr)
memcpy(optr, data(sv), sz(sv)), optr += sz(sv);
else {
flush();
for (auto *p = data(sv), *pe = p + sz(sv); p != pe; p += write(STDOUT_FILENO, p, pe - p));
}
} else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T2>)
return print(decltype(T2::mod())(val));
else if constexpr (cp_lib_type_meta::is_tuple_like<T2> && !is_std_array<T2>)
return apply([](auto&&... items) { (print(items), ...); }, forward<T>(val));
else {
trav(item, val)
print(item);
return;
}
*optr++ = ' ';
}
template <class T>
void read(T& val) {
auto skip_ws = [] {
do {
for (; iptr != iend && *iptr <= ' '; ++iptr);
if (iend - iptr < 64)
refill();
} while (*iptr <= ' ');
};
auto read_other = [&](auto other) {
read(other);
return other;
};
if constexpr (is_same_v<T, char>)
skip_ws(), val = *iptr++;
else if constexpr (is_same_v<T, bool> || is_same_v<T, vector<bool>::reference>) {
val = bool(read_other(uint8_t()));
} else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T>) {
val = T(read_other(ll()));
} else if constexpr (is_integral_v<T>) {
skip_ws();
if (is_signed_v<T> && *iptr == '-')
++iptr, val = T(-read_other(make_unsigned_t<T>()));
else
for (val = 0; iptr != iend && *iptr > ' '; val = T(10 * val + (*iptr++ & 15)));
} else if constexpr (is_floating_point_v<T>)
skip_ws(), val = T(strtold(iptr, &iptr));
else if constexpr (is_same_v<T, string>) {
skip_ws();
val.clear();
do {
auto* after = find_if(iptr, iend, [](char c) { return c <= ' '; });
val.append(iptr, after);
if ((iptr = after) != iend)
break;
refill();
} while (iptr != iend);
} else if constexpr (cp_lib_type_meta::is_tuple_like<T> && !is_std_array<T>)
apply([](auto&... items) { (read(items), ...); }, val);
else
trav(item, val)
read(item);
}
}
using cp_lib_io::flush;
template <class... Args>
void print(Args&&... args) { (cp_lib_io::print(forward<Args>(args)), ...); }
template <class... Args>
void println(Args&&... args) {
if (sizeof...(Args))
(cp_lib_io::print(forward<Args>(args)), ...), *(cp_lib_io::optr - 1) = '\n';
else
print('\n'), --cp_lib_io::optr;
}
template <class... Args>
void read(Args&... args) { (cp_lib_io::read(args), ...); }
template <class I>
constexpr enable_if_t<is_signed_v<I>, array<I, 3>> ext_gcd(I a, I b) {
I x(1), y(0), x1(0), y1(1);
while (b) {
I t = a / b;
tie(x, x1) = pair(x1, x - t * x1);
tie(y, y1) = pair(y1, y - t * y1);
tie(a, b) = pair(b, a - t * b);
}
return {a, x, y};
}
namespace cp_lib_modint {
template <class Self, class Int>
struct Base : ModIntTag {
static_assert(is_same_v<Int, uint32_t> || is_same_v<Int, uint64_t>);
friend constexpr Self operator+(Self l, Self r) { return l += r; }
friend constexpr Self operator-(Self l, Self r) { return l -= r; }
friend constexpr Self operator*(Self l, Self r) { return l *= r; }
friend constexpr Self operator/(Self l, Self r) { return l * r.inv(); }
friend constexpr Self& operator/=(Self& l, Self r) { return l *= r.inv(); }
friend constexpr Self operator+(Self x) { return x; }
friend constexpr Self operator-(Self x) { return Self(0) - x; }
friend constexpr Self& operator++(Self& x) { return x += Self(1); }
friend constexpr Self& operator--(Self& x) { return x -= Self(1); }
friend constexpr Self operator++(Self& x, int) { auto y = x; ++x; return y; }
friend constexpr Self operator--(Self& x, int) { auto y = x; --x; return y; }
#define CP_LIB_DEF(op) \
template <class T, enable_if_t<is_integral_v<T>, int> = 0> \
friend constexpr auto operator op(T l, Self r) { return Self(l) op r; }
CP_LIB_DEF(==) CP_LIB_DEF(!=) CP_LIB_DEF(<) CP_LIB_DEF(+) CP_LIB_DEF(-) CP_LIB_DEF(*) CP_LIB_DEF(/)
#undef CP_LIB_DEF
template <class T>
constexpr enable_if_t<is_integral_v<T>, Self> pow(T e) const {
Self r(1), b(*(Self*)(this));
for (; e; b *= b, e >>= 1)
if (e & 1) r *= b;
return r;
}
constexpr optional<Self> try_inv() const {
if (Self::is_prime())
return *(Self*)this == Self() ? nullopt : optional(pow(Self::mod() - 2));
auto [g, x, _] = ext_gcd(ll(*(Self*)this), ll(Self::mod()));
return (abs(g) == 1 ? optional(Self(x)) : nullopt);
}
constexpr Self inv() const {
if (Self::is_prime()) return pow(Self::mod() - 2);
auto [g, x, _] = ext_gcd(ll(*(Self*)this), ll(Self::mod()));
cp_lib_assert(abs(g) == 1);
return x;
}
friend ostream& operator<<(ostream& out, Self m) { return out << uint64_t(m); }
friend istream& operator>>(istream& in, Self& m) { ll x; in >> x; m = x; return in; }
protected:
Int i = 0;
};
template <class Int> using Wide = conditional_t<is_same_v<uint64_t, Int>, unsigned __int128, uint64_t>;
}
namespace cp_lib_modint {
template <class Int, Int Mod, bool IsPrime>
struct StaticMontgomery : public Base<StaticMontgomery<Int, Mod, IsPrime>, Int> {
static_assert(Mod % 2 && Mod < (1ull << (sizeof(Int) * 8 - 2)));
static constexpr Int INV = []{
Int inv = Mod;
rep(_, __builtin_ctz(sizeof(Int) * 8) - 1) inv *= 2 - Mod * inv;
return inv;
}();
static constexpr Int R2 = Int(-Wide<Int>(Mod) % Mod);
static constexpr Int reduce(Wide<Int> x) {
return Int((x - Int(x) * INV * Wide<Int>(Mod)) >> (sizeof(Int) * 8)) + Mod;
}
static constexpr Int norm(Int x) { return x >= Mod ? x - Mod : x; }
static constexpr Int mod() { return Mod; }
static constexpr bool is_prime() { return IsPrime; }
StaticMontgomery() = default;
template <class T, enable_if_t<is_unsigned_v<T>, int> = 0>
constexpr StaticMontgomery(T x) { this->i = reduce(Wide<Int>(uint64_t(x) % Mod) * R2); }
template <class T, enable_if_t<is_signed_v<T>, int> = 0>
constexpr StaticMontgomery(T x) { this->i = reduce(Wide<Int>(ll(x) % ll(Mod) + ll(Mod)) * R2); }
template <class T, enable_if_t<is_integral_v<T>, int> = 0>
constexpr explicit operator T() const { return T(norm(reduce(this->i))); }
constexpr Int raw() const { return norm(this->i); }
constexpr bool operator==(StaticMontgomery r) const { return norm(this->i) == norm(r.i); }
constexpr bool operator!=(StaticMontgomery r) const { return norm(this->i) != norm(r.i); }
constexpr bool operator<(StaticMontgomery r) const { return norm(this->i) < norm(r.i); }
constexpr StaticMontgomery& operator+=(StaticMontgomery r) {
if ((this->i += r.i) >= 2 * Mod)
this->i -= 2 * Mod;
return *this;
}
constexpr StaticMontgomery& operator-=(StaticMontgomery r) {
if (make_signed_t<Int>(this->i -= r.i) < 0)
this->i += 2 * Mod;
return *this;
}
constexpr StaticMontgomery& operator*=(StaticMontgomery r) {
this->i = reduce(Wide<Int>(this->i) * r.i);
return *this;
}
};
}
template <uint32_t Mod, bool IsPrime> using StaticMontgomeryInt = cp_lib_modint::StaticMontgomery<uint32_t, Mod, IsPrime>;
template <uint64_t Mod, bool IsPrime> using StaticMontgomeryInt64 = cp_lib_modint::StaticMontgomery<uint64_t, Mod, IsPrime>;
template <class T> constexpr inline bool is_pow2(T n) { return n && !(n & (n - 1)); }
template <class T> constexpr inline int floor_log2(T n) { return n ? 63 - __builtin_clzll(n) : 0; }
template <class T> constexpr inline int ceil_log2(T n) { return n ? floor_log2(n) + !is_pow2(n) : 0; }
template <class MI>
class NumberTheoreticTransform {
int max_exp;
array<array<array<MI, 30>, 31>, 2> z_step{};
public:
explicit NumberTheoreticTransform(MI g) : max_exp(min(30, __builtin_ctzll(MI::mod() - 1))) {
rep(w, max_exp) {
auto z_w = g.pow((MI::mod() - 1) >> (w + 1));
rep(i, w) {
int diff = (1 << (w - 1 - i)) - (((1 << i) - 1) << (w - i));
auto z = z_w.pow(abs(diff));
rep(inv, 2)
z_step[inv][w][i] = ((diff < 0) ^ inv ? z.inv() : z);
}
}
}
template <class It, class ItEnd>
void ntt_to_rev(It it, ItEnd it_end) const {
int n = int(it_end - it);
cp_lib_assert(is_pow2(n) && __builtin_ctz(n) <= max_exp);
for (int k = n >> 1, w = 0; k; k >>= 1, ++w) {
MI z = 1, a1;
for (int i = 0, x = 0; i < n; i += (k << 1), z *= z_step[0][w][__builtin_ctz(~x++)])
rep(j, i, i + k)
a1 = it[j + k] * z, it[j + k] = it[j] - a1, it[j] += a1;
}
}
template <class It, class ItEnd>
void intt_from_rev(It it, ItEnd it_end) const {
int n = int(it_end - it);
cp_lib_assert(is_pow2(n) && __builtin_ctz(n) <= max_exp);
for (int k = 1, w = __builtin_ctz(n) - 1; k < n; k <<= 1, --w) {
MI z = 1, a1;
for (int i = 0, x = 3 << w; i < n; i += 2 * k, z *= z_step[1][w][__builtin_ctz(--x)])
rep(j, i, i + k)
a1 = it[j + k], it[j + k] = (it[j] - a1) * z, it[j] += a1;
}
}
template <class ItA, class ItAEnd, class ItB, class ItBEnd>
vector<MI> convolution(ItA it_a, ItAEnd it_a_end, ItB it_b, ItBEnd it_b_end) const {
int la = int(it_a_end - it_a), lb = int(it_b_end - it_b), n = 1 << ceil_log2(la + lb - 1);
if (!la || !lb)
return {};
if (min(la, lb) < 32) {
vector<MI> a(la), b(lb), r(la + lb - 1);
transform(it_a, it_a_end, begin(a), [](auto&& x) { return MI(x); });
transform(it_b, it_b_end, begin(b), [](auto&& x) { return MI(x); });
rep(i, la) rep(j, lb)
r[i + j] += a[i] * b[j];
return r;
}
vector<MI> f(n), g(n);
transform(it_a, it_a_end, begin(f), [](auto&& x) { return MI(x); });
transform(it_b, it_b_end, begin(g), [](auto&& x) { return MI(x); });
ntt_to_rev(all(f));
ntt_to_rev(all(g));
auto inv_n = MI(n).inv();
rep(i, n)
f[i] *= g[i] * inv_n;
intt_from_rev(all(f));
f.resize(la + lb - 1);
return f;
}
};
template <class MI>
struct Combinatorics {
vector<MI> f, fi;
explicit Combinatorics(int n) : f(n + 1), fi(n + 1) {
f[0] = 1;
MI m; int i;
for (i = 1, m = f[0]; i <= n; ++i, ++m)
f[i] = f[i - 1] * m;
fi[n] = f[n].inv();
for (--i, --m; i; --i, --m)
fi[i - 1] = m * fi[i];
}
MI binom(int n, int k) const { return (n >= k && k >= 0 ? f[n] * fi[n - k] * fi[k] : MI(0)); }
MI stars_bars(int n, int k) const { return binom(n + k - 1, k - 1); }
MI catalan(int n) const { return f[2 * n] * fi[n + 1] * fi[n]; }
MI catalan(int n, int k) const { return (k ? k * f[2 * n + k - 1] * fi[n + k] * fi[n] : MI(!n)); }
template <class It, class ItEnd>
MI multinom(int n, It it, ItEnd it_end) const {
MI res = f[n];
while (it != it_end) res *= fi[*it++];
return res;
}
};
template <class MI>
vector<MI> taylor_shift(const vector<MI>& a, MI c, const Combinatorics<MI>& binom,
const NumberTheoreticTransform<MI>& ntt) {
int n = sz(a);
vector<MI> f(n), g(n);
MI pow_c = 1;
rep(i, n)
f[i] = binom.f[i] * a[i], g[n - 1 - i] = pow_c * binom.fi[i], pow_c *= c;
auto h = ntt.convolution(all(f), all(g));
rep(i, n)
f[i] = h[n + i - 1] * binom.fi[i];
return f;
}
template <class MI>
vector<MI> stirling_1st_kind(int n, const Combinatorics<MI>& binom,
const NumberTheoreticTransform<MI>& ntt) {
if (!n)
return {1};
auto a = stirling_1st_kind<MI>(n / 2, binom, ntt);
auto b = taylor_shift(a, -MI(n / 2), binom, ntt);
a = ntt.convolution(all(a), all(b));
if (n % 2)
b = {-MI(n - 1), 1}, a = ntt.convolution(all(a), all(b));
return a;
}
// https://judge.yosupo.jp/submission/77453
int main() {
int n; cin >> n;
using MI = StaticMontgomeryInt<998'244'353, true>;
NumberTheoreticTransform ntt(MI(3));
Combinatorics<MI> binom(n);
auto a = stirling_1st_kind(n, binom, ntt);
MI ans = 0;
for (int i = 1; i <= n; ++i) {
ans += ((n ^ i) & 1 ? -a[i] : a[i]) * i * i * i;
}
cout << ans << '\n';
return 0;
// FOR(n, 1, N) {
// vector<int> ways(n + 1, 0), a(n);
// iota(ALL(a), 0);
// do {
// int f = 0, max = -1;
// REP(i, n) f += chmax(max, a[i]);
// ++ways[f];
// } while (next_permutation(ALL(a)));
// REP(i, n + 1) cout << ways[i] << " \n"[i == n];
// }
}