結果
問題 | No.2514 Twelvefold Way Returns |
ユーザー |
|
提出日時 | 2023-10-20 23:34:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 418 ms / 3,000 ms |
コード長 | 52,746 bytes |
コンパイル時間 | 5,531 ms |
コンパイル使用メモリ | 244,424 KB |
最終ジャッジ日時 | 2025-02-17 11:14:53 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>namespace suisen {template <class T> bool chmin(T& x, const T& y) { return y >= x ? false : (x = y, true); }template <class T> bool chmax(T& x, const T& y) { return y <= x ? false : (x = y, true); }template <class T> constexpr int pow_m1(T n) { return -(n & 1) | 1; }template <class T> constexpr T fld(const T x, const T y) { T q = x / y, r = x % y; return q - ((x ^ y) < 0 and (r != 0)); }template <class T> constexpr T cld(const T x, const T y) { T q = x / y, r = x % y; return q + ((x ^ y) > 0 and (r != 0)); }}namespace suisen::macro {#define IMPL_REPITER(cond) auto& begin() { return *this; } auto end() { return nullptr; } auto& operator*() { return _val; } auto& operator++() {return _val += _step, *this; } bool operator!=(std::nullptr_t) { return cond; }template <class Int, class IntL = Int, class IntStep = Int, std::enable_if_t<(std::is_signed_v<Int> == std::is_signed_v<IntL>), std::nullptr_t>= nullptr> struct rep_impl {Int _val; const Int _end, _step;rep_impl(Int n) : rep_impl(0, n) {}rep_impl(IntL l, Int r, IntStep step = 1) : _val(l), _end(r), _step(step) {}IMPL_REPITER((_val < _end))};template <class Int, class IntL = Int, class IntStep = Int, std::enable_if_t<(std::is_signed_v<Int> == std::is_signed_v<IntL>), std::nullptr_t>= nullptr> struct rrep_impl {Int _val; const Int _end, _step;rrep_impl(Int n) : rrep_impl(0, n) {}rrep_impl(IntL l, Int r) : _val(r - 1), _end(l), _step(-1) {}rrep_impl(IntL l, Int r, IntStep step) : _val(l + fld<Int>(r - l - 1, step) * step), _end(l), _step(-step) {}IMPL_REPITER((_val >= _end))};template <class Int, class IntStep = Int> struct repinf_impl {Int _val; const Int _step;repinf_impl(Int l, IntStep step = 1) : _val(l), _step(step) {}IMPL_REPITER((true))};#undef IMPL_REPITER}#include <iostream>#include <limits>#include <type_traits>namespace suisen {template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };template <typename T> static constexpr int bitnum_v = bitnum<T>::value;template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;template <typename T, typename = void> struct rec_value_type { using type = T; };template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {using type = typename rec_value_type<typename T::value_type>::type;};template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;template <typename T> class is_iterable {template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});static std::false_type test(...);public:static constexpr bool value = decltype(test(std::declval<T>()))::value;};template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;template <typename T> class is_writable {template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});static std::false_type test(...);public:static constexpr bool value = decltype(test(std::declval<T>()))::value;};template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;template <typename T> class is_readable {template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});static std::false_type test(...);public:static constexpr bool value = decltype(test(std::declval<T>()))::value;};template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;} // namespace suisennamespace suisen::io {template <typename IStream, std::enable_if_t<std::conjunction_v<std::is_base_of<std::istream, std::remove_reference_t<IStream>>, std::negation<std::is_const<std::remove_reference_t<IStream>>>>, std::nullptr_t> = nullptr>struct InputStream {private:using istream_type = std::remove_reference_t<IStream>;IStream is;struct { InputStream* is; template <typename T> operator T() { T e; *is >> e; return e; } } _reader{ this };public:template <typename IStream_> InputStream(IStream_ &&is) : is(std::move(is)) {}template <typename IStream_> InputStream(IStream_ &is) : is(is) {}template <typename T> InputStream& operator>>(T& e) {if constexpr (suisen::is_readable_v<T>) is >> e; else _read(e);return *this;}auto read() { return _reader; }template <typename Head, typename... Tail>void read(Head& head, Tail &...tails) { ((*this >> head) >> ... >> tails); }istream_type& get_stream() { return is; }private:static __uint128_t _stou128(const std::string& s) {__uint128_t ret = 0;for (char c : s) if ('0' <= c and c <= '9') ret = 10 * ret + c - '0';return ret;}static __int128_t _stoi128(const std::string& s) { return (s[0] == '-' ? -1 : +1) * _stou128(s); }void _read(__uint128_t& v) { v = _stou128(std::string(_reader)); }void _read(__int128_t& v) { v = _stoi128(std::string(_reader)); }template <typename T, typename U>void _read(std::pair<T, U>& a) { *this >> a.first >> a.second; }template <size_t N = 0, typename ...Args>void _read(std::tuple<Args...>& a) { if constexpr (N < sizeof...(Args)) *this >> std::get<N>(a), _read<N + 1>(a); }template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>void _read(Iterable& a) { for (auto& e : a) *this >> e; }};template <typename IStream>InputStream(IStream &&) -> InputStream<IStream>;template <typename IStream>InputStream(IStream &) -> InputStream<IStream&>;InputStream cin{ std::cin };auto read() { return cin.read(); }template <typename Head, typename... Tail>void read(Head& head, Tail &...tails) { cin.read(head, tails...); }} // namespace suisen::ionamespace suisen { using io::read; } // namespace suisennamespace suisen::io {template <typename OStream, std::enable_if_t<std::conjunction_v<std::is_base_of<std::ostream, std::remove_reference_t<OStream>>, std::negation<std::is_const<std::remove_reference_t<OStream>>>>, std::nullptr_t> = nullptr>struct OutputStream {private:using ostream_type = std::remove_reference_t<OStream>;OStream os;public:template <typename OStream_> OutputStream(OStream_ &&os) : os(std::move(os)) {}template <typename OStream_> OutputStream(OStream_ &os) : os(os) {}template <typename T> OutputStream& operator<<(const T& e) {if constexpr (suisen::is_writable_v<T>) os << e; else _print(e);return *this;}void print() { *this << '\n'; }template <typename Head, typename... Tail>void print(const Head& head, const Tail &...tails) { *this << head, ((*this << ' ' << tails), ...), *this << '\n'; }template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>void print_all(const Iterable& v, std::string sep = " ", std::string end = "\n") {for (auto it = v.begin(); it != v.end();) if (*this << *it; ++it != v.end()) *this << sep;*this << end;}ostream_type& get_stream() { return os; }private:void _print(__uint128_t value) {char buffer[41], *d = std::end(buffer);do *--d = '0' + (value % 10), value /= 10; while (value);os.rdbuf()->sputn(d, std::end(buffer) - d);}void _print(__int128_t value) {if (value < 0) *this << '-';_print(__uint128_t(value < 0 ? -value : value));}template <typename T, typename U>void _print(const std::pair<T, U>& a) { *this << a.first << ' ' << a.second; }template <size_t N = 0, typename ...Args>void _print(const std::tuple<Args...>& a) {if constexpr (N < std::tuple_size_v<std::tuple<Args...>>) {if constexpr (N) *this << ' ';*this << std::get<N>(a), _print<N + 1>(a);}}template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>void _print(const Iterable& a) { print_all(a, " ", ""); }};template <typename OStream_>OutputStream(OStream_ &&) -> OutputStream<OStream_>;template <typename OStream_>OutputStream(OStream_ &) -> OutputStream<OStream_&>;OutputStream cout{ std::cout }, cerr{ std::cerr };template <typename... Args>void print(const Args &... args) { cout.print(args...); }template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>void print_all(const Iterable& v, const std::string& sep = " ", const std::string& end = "\n") { cout.print_all(v, sep, end); }} // namespace suisen::ionamespace suisen { using io::print, io::print_all; } // namespace suisennamespace suisen {template <class T, class ToKey, class CompKey = std::less<>, std::enable_if_t<std::conjunction_v<std::is_invocable<ToKey, T>, std::is_invocable_r<bool, CompKey, std::invoke_result_t<ToKey, T>, std::invoke_result_t<ToKey, T>>>, std::nullptr_t> = nullptr>auto comparator(const ToKey& to_key, const CompKey& comp_key = std::less<>()) {return [=](const T& x, const T& y) { return comp_key(to_key(x), to_key(y)); };}template <class Compare, std::enable_if_t<std::is_invocable_r_v<bool, Compare, int, int>, std::nullptr_t> = nullptr>std::vector<int> sorted_indices(int n, const Compare& compare) {std::vector<int> p(n);return std::iota(p.begin(), p.end(), 0), std::sort(p.begin(), p.end(), compare), p;}template <class ToKey, std::enable_if_t<std::is_invocable_v<ToKey, int>, std::nullptr_t> = nullptr>std::vector<int> sorted_indices(int n, const ToKey& to_key) { return sorted_indices(n, comparator<int>(to_key)); }template <class T, class Comparator>auto priority_queue_with_comparator(const Comparator& comparator) { return std::priority_queue<T, std::vector<T>, Comparator>{ comparator }; }template <class Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>void sort_unique_erase(Iterable& a) { std::sort(a.begin(), a.end()), a.erase(std::unique(a.begin(), a.end()), a.end()); }template <size_t D> struct Dim : std::array<int, D> {template <typename ...Ints> Dim(const Ints& ...ns) : std::array<int, D>::array{ static_cast<int>(ns)... } {}};template <typename ...Ints> Dim(const Ints& ...) -> Dim<sizeof...(Ints)>;template <class T, size_t D, size_t I = 0>auto ndvec(const Dim<D> &ns, const T& value = {}) {if constexpr (I + 1 < D) {return std::vector(ns[I], ndvec<T, D, I + 1>(ns, value));} else {return std::vector<T>(ns[I], value);}}}namespace suisen {using int128 = __int128_t;using uint128 = __uint128_t;template <class T> using min_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T>>;template <class T> using max_priority_queue = std::priority_queue<T, std::vector<T>, std::less<T>>;}namespace suisen { const std::string Yes = "Yes", No = "No", YES = "YES", NO = "NO"; }#ifdef LOCAL# define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__)template <class H, class... Ts> void debug_impl(const char* s, const H& h, const Ts&... t) {suisen::io::cerr << "[\033[32mDEBUG\033[m] " << s << ": " << h, ((suisen::io::cerr << ", " << t), ..., (suisen::io::cerr << "\n"));}#else# define debug(...) void(0)#endif#define FOR(e, v) for (auto &&e : v)#define CFOR(e, v) for (const auto &e : v)#define REP(i, ...) CFOR(i, suisen::macro::rep_impl(__VA_ARGS__))#define RREP(i, ...) CFOR(i, suisen::macro::rrep_impl(__VA_ARGS__))#define REPINF(i, ...) CFOR(i, suisen::macro::repinf_impl(__VA_ARGS__))#define LOOP(n) for ([[maybe_unused]] const auto& _ : suisen::macro::rep_impl(n))#define ALL(iterable) std::begin(iterable), std::end(iterable)using namespace suisen;using namespace std;struct io_setup {io_setup(int precision = 20) {std::ios::sync_with_stdio(false), std::cin.tie(nullptr);std::cout << std::fixed << std::setprecision(precision);}} io_setup_{};constexpr int iinf = std::numeric_limits<int>::max() / 2;constexpr long long linf = std::numeric_limits<long long>::max() / 2;#include <atcoder/modint>using mint = atcoder::modint998244353;namespace atcoder {std::istream& operator>>(std::istream& in, mint &a) {long long e; in >> e; a = e;return in;}std::ostream& operator<<(std::ostream& out, const mint &a) {out << a.val();return out;}} // namespace atcoder#include <optional>#include <queue>#include <atcoder/modint>#include <atcoder/convolution>#include <cassert>#include <cmath>#include <vector>/*** refernce: https://37zigen.com/tonelli-shanks-algorithm/* calculates x s.t. x^2 = a mod p in O((log p)^2).*/template <typename mint>std::optional<mint> safe_sqrt(mint a) {static int p = mint::mod();if (a == 0) return std::make_optional(0);if (p == 2) return std::make_optional(a);if (a.pow((p - 1) / 2) != 1) return std::nullopt;mint b = 1;while (b.pow((p - 1) / 2) == 1) ++b;static int tlz = __builtin_ctz(p - 1), q = (p - 1) >> tlz;mint x = a.pow((q + 1) / 2);b = b.pow(q);for (int shift = 2; x * x != a; ++shift) {mint e = a.inv() * x * x;if (e.pow(1 << (tlz - shift)) != 1) x *= b;b *= b;}return std::make_optional(x);}/*** calculates x s.t. x^2 = a mod p in O((log p)^2).* if not exists, raises runtime error.*/template <typename mint>auto sqrt(mint a) -> decltype(mint::mod(), mint()) {return *safe_sqrt(a);}template <typename mint>auto log(mint a) -> decltype(mint::mod(), mint()) {assert(a == 1);return 0;}template <typename mint>auto exp(mint a) -> decltype(mint::mod(), mint()) {assert(a == 0);return 1;}template <typename mint, typename T>auto pow(mint a, T b) -> decltype(mint::mod(), mint()) {return a.pow(b);}template <typename mint>auto inv(mint a) -> decltype(mint::mod(), mint()) {return a.inv();}namespace suisen {template <typename mint>class inv_mods {public:inv_mods() = default;inv_mods(int n) { ensure(n); }const mint& operator[](int i) const {ensure(i);return invs[i];}static void ensure(int n) {int sz = invs.size();if (sz < 2) invs = { 0, 1 }, sz = 2;if (sz < n + 1) {invs.resize(n + 1);for (int i = sz; i <= n; ++i) invs[i] = mint(mod - mod / i) * invs[mod % i];}}private:static std::vector<mint> invs;static constexpr int mod = mint::mod();};template <typename mint>std::vector<mint> inv_mods<mint>::invs{};template <typename mint>std::vector<mint> get_invs(const std::vector<mint>& vs) {const int n = vs.size();mint p = 1;for (auto& e : vs) {p *= e;assert(e != 0);}mint ip = p.inv();std::vector<mint> rp(n + 1);rp[n] = 1;for (int i = n - 1; i >= 0; --i) {rp[i] = rp[i + 1] * vs[i];}std::vector<mint> res(n);for (int i = 0; i < n; ++i) {res[i] = ip * rp[i + 1];ip *= vs[i];}return res;}}namespace suisen {template <typename T>struct FPSNaive : std::vector<T> {static inline int MAX_SIZE = std::numeric_limits<int>::max() / 2;using value_type = T;using element_type = rec_value_type_t<T>;using std::vector<value_type>::vector;FPSNaive(const std::initializer_list<value_type> l) : std::vector<value_type>::vector(l) {}FPSNaive(const std::vector<value_type>& v) : std::vector<value_type>::vector(v) {}static void set_max_size(int n) {FPSNaive<T>::MAX_SIZE = n;}const value_type operator[](int n) const {return n <= deg() ? unsafe_get(n) : value_type{ 0 };}value_type& operator[](int n) {return ensure_deg(n), unsafe_get(n);}int size() const {return std::vector<value_type>::size();}int deg() const {return size() - 1;}int normalize() {while (size() and this->back() == value_type{ 0 }) this->pop_back();return deg();}FPSNaive& cut_inplace(int n) {if (size() > n) this->resize(std::max(0, n));return *this;}FPSNaive cut(int n) const {FPSNaive f = FPSNaive(*this).cut_inplace(n);return f;}FPSNaive operator+() const {return FPSNaive(*this);}FPSNaive operator-() const {FPSNaive f(*this);for (auto& e : f) e = -e;return f;}FPSNaive& operator++() { return ++(*this)[0], * this; }FPSNaive& operator--() { return --(*this)[0], * this; }FPSNaive& operator+=(const value_type x) { return (*this)[0] += x, *this; }FPSNaive& operator-=(const value_type x) { return (*this)[0] -= x, *this; }FPSNaive& operator+=(const FPSNaive& g) {ensure_deg(g.deg());for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) += g.unsafe_get(i);return *this;}FPSNaive& operator-=(const FPSNaive& g) {ensure_deg(g.deg());for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) -= g.unsafe_get(i);return *this;}FPSNaive& operator*=(const FPSNaive& g) { return *this = *this * g; }FPSNaive& operator*=(const value_type x) {for (auto& e : *this) e *= x;return *this;}FPSNaive& operator/=(const FPSNaive& g) { return *this = *this / g; }FPSNaive& operator%=(const FPSNaive& g) { return *this = *this % g; }FPSNaive& operator<<=(const int shamt) {this->insert(this->begin(), shamt, value_type{ 0 });return *this;}FPSNaive& operator>>=(const int shamt) {if (shamt > size()) this->clear();else this->erase(this->begin(), this->begin() + shamt);return *this;}friend FPSNaive operator+(FPSNaive f, const FPSNaive& g) { f += g; return f; }friend FPSNaive operator+(FPSNaive f, const value_type& x) { f += x; return f; }friend FPSNaive operator-(FPSNaive f, const FPSNaive& g) { f -= g; return f; }friend FPSNaive operator-(FPSNaive f, const value_type& x) { f -= x; return f; }friend FPSNaive operator*(const FPSNaive& f, const FPSNaive& g) {if (f.empty() or g.empty()) return FPSNaive{};const int n = f.size(), m = g.size();FPSNaive h(std::min(MAX_SIZE, n + m - 1));for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {if (i + j >= MAX_SIZE) break;h.unsafe_get(i + j) += f.unsafe_get(i) * g.unsafe_get(j);}return h;}friend FPSNaive operator*(FPSNaive f, const value_type& x) { f *= x; return f; }friend FPSNaive operator/(FPSNaive f, const FPSNaive& g) { return std::move(f.div_mod(g).first); }friend FPSNaive operator%(FPSNaive f, const FPSNaive& g) { return std::move(f.div_mod(g).second); }friend FPSNaive operator*(const value_type x, FPSNaive f) { f *= x; return f; }friend FPSNaive operator<<(FPSNaive f, const int shamt) { f <<= shamt; return f; }friend FPSNaive operator>>(FPSNaive f, const int shamt) { f >>= shamt; return f; }std::pair<FPSNaive, FPSNaive> div_mod(FPSNaive g) const {FPSNaive f = *this;const int fd = f.normalize(), gd = g.normalize();assert(gd >= 0);if (fd < gd) return { FPSNaive{}, f };if (gd == 0) return { f *= g.unsafe_get(0).inv(), FPSNaive{} };const int k = f.deg() - gd;value_type head_inv = g.unsafe_get(gd).inv();FPSNaive q(k + 1);for (int i = k; i >= 0; --i) {value_type div = f.unsafe_get(i + gd) * head_inv;q.unsafe_get(i) = div;for (int j = 0; j <= gd; ++j) f.unsafe_get(i + j) -= div * g.unsafe_get(j);}f.cut_inplace(gd);f.normalize();return { q, f };}friend bool operator==(const FPSNaive& f, const FPSNaive& g) {const int n = f.size(), m = g.size();if (n < m) return g == f;for (int i = 0; i < m; ++i) if (f.unsafe_get(i) != g.unsafe_get(i)) return false;for (int i = m; i < n; ++i) if (f.unsafe_get(i) != 0) return false;return true;}friend bool operator!=(const FPSNaive& f, const FPSNaive& g) {return not (f == g);}FPSNaive mul(const FPSNaive& g, int n = -1) const {if (n < 0) n = size();if (this->empty() or g.empty()) return FPSNaive{};const int m = size(), k = g.size();FPSNaive h(std::min(n, m + k - 1));for (int i = 0; i < m; ++i) {for (int j = 0, jr = std::min(k, n - i); j < jr; ++j) {h.unsafe_get(i + j) += unsafe_get(i) * g.unsafe_get(j);}}return h;}FPSNaive diff() const {if (this->empty()) return {};FPSNaive g(size() - 1);for (int i = 1; i <= deg(); ++i) g.unsafe_get(i - 1) = unsafe_get(i) * i;return g;}FPSNaive intg() const {const int n = size();FPSNaive g(n + 1);for (int i = 0; i < n; ++i) g.unsafe_get(i + 1) = unsafe_get(i) * invs[i + 1];if (g.deg() > MAX_SIZE) g.cut_inplace(MAX_SIZE);return g;}FPSNaive inv(int n = -1) const {if (n < 0) n = size();FPSNaive g(n);const value_type inv_f0 = ::inv(unsafe_get(0));g.unsafe_get(0) = inv_f0;for (int i = 1; i < n; ++i) {for (int j = 1; j <= i; ++j) g.unsafe_get(i) -= g.unsafe_get(i - j) * (*this)[j];g.unsafe_get(i) *= inv_f0;}return g;}FPSNaive exp(int n = -1) const {if (n < 0) n = size();assert(unsafe_get(0) == value_type{ 0 });FPSNaive g(n);g.unsafe_get(0) = value_type{ 1 };for (int i = 1; i < n; ++i) {for (int j = 1; j <= i; ++j) g.unsafe_get(i) += j * g.unsafe_get(i - j) * (*this)[j];g.unsafe_get(i) *= invs[i];}return g;}FPSNaive log(int n = -1) const {if (n < 0) n = size();assert(unsafe_get(0) == value_type{ 1 });FPSNaive g(n);g.unsafe_get(0) = value_type{ 0 };for (int i = 1; i < n; ++i) {g.unsafe_get(i) = i * (*this)[i];for (int j = 1; j < i; ++j) g.unsafe_get(i) -= (i - j) * g.unsafe_get(i - j) * (*this)[j];g.unsafe_get(i) *= invs[i];}return g;}FPSNaive pow(const long long k, int n = -1) const {if (n < 0) n = size();if (k == 0) {FPSNaive res(n);res[0] = 1;return res;}int z = 0;while (z < size() and unsafe_get(z) == value_type{ 0 }) ++z;if (z == size() or z > (n - 1) / k) return FPSNaive(n, 0);const int m = n - z * k;FPSNaive g(m);const value_type inv_f0 = ::inv(unsafe_get(z));g.unsafe_get(0) = unsafe_get(z).pow(k);for (int i = 1; i < m; ++i) {for (int j = 1; j <= i; ++j) g.unsafe_get(i) += (element_type{ k } *j - (i - j)) * g.unsafe_get(i - j) * (*this)[z + j];g.unsafe_get(i) *= inv_f0 * invs[i];}g <<= z * k;return g;}std::optional<FPSNaive> safe_sqrt(int n = -1) const {if (n < 0) n = size();int dl = 0;while (dl < size() and unsafe_get(dl) == value_type{ 0 }) ++dl;if (dl == size()) return FPSNaive(n, 0);if (dl & 1) return std::nullopt;const int m = n - dl / 2;FPSNaive g(m);auto opt_g0 = ::safe_sqrt((*this)[dl]);if (not opt_g0.has_value()) return std::nullopt;g.unsafe_get(0) = *opt_g0;value_type inv_2g0 = ::inv(2 * g.unsafe_get(0));for (int i = 1; i < m; ++i) {g.unsafe_get(i) = (*this)[dl + i];for (int j = 1; j < i; ++j) g.unsafe_get(i) -= g.unsafe_get(j) * g.unsafe_get(i - j);g.unsafe_get(i) *= inv_2g0;}g <<= dl / 2;return g;}FPSNaive sqrt(int n = -1) const {if (n < 0) n = size();return *safe_sqrt(n);}value_type eval(value_type x) const {value_type y = 0;for (int i = size() - 1; i >= 0; --i) y = y * x + unsafe_get(i);return y;}private:static inline inv_mods<element_type> invs;void ensure_deg(int d) {if (deg() < d) this->resize(d + 1, value_type{ 0 });}const value_type& unsafe_get(int i) const {return std::vector<value_type>::operator[](i);}value_type& unsafe_get(int i) {return std::vector<value_type>::operator[](i);}};} // namespace suisentemplate <typename mint>suisen::FPSNaive<mint> sqrt(suisen::FPSNaive<mint> a) {return a.sqrt();}template <typename mint>suisen::FPSNaive<mint> log(suisen::FPSNaive<mint> a) {return a.log();}template <typename mint>suisen::FPSNaive<mint> exp(suisen::FPSNaive<mint> a) {return a.exp();}template <typename mint, typename T>suisen::FPSNaive<mint> pow(suisen::FPSNaive<mint> a, T b) {return a.pow(b);}template <typename mint>suisen::FPSNaive<mint> inv(suisen::FPSNaive<mint> a) {return a.inv();}namespace suisen {template <typename mint, atcoder::internal::is_static_modint_t<mint>* = nullptr>struct FormalPowerSeries : std::vector<mint> {using base_type = std::vector<mint>;using value_type = typename base_type::value_type;using base_type::vector;FormalPowerSeries(const std::initializer_list<value_type> l) : std::vector<value_type>::vector(l) {}FormalPowerSeries(const std::vector<value_type>& v) : std::vector<value_type>::vector(v) {}int size() const noexcept {return base_type::size();}int deg() const noexcept {return size() - 1;}void ensure(int n) {if (size() < n) this->resize(n);}value_type safe_get(int d) const {return d <= deg() ? (*this)[d] : 0;}value_type& safe_get(int d) {ensure(d + 1);return (*this)[d];}FormalPowerSeries& cut_trailing_zeros() {while (size() and this->back() == 0) this->pop_back();return *this;}FormalPowerSeries& cut(int n) {if (size() > n) this->resize(std::max(0, n));return *this;}FormalPowerSeries cut_copy(int n) const {FormalPowerSeries res(this->begin(), this->begin() + std::min(size(), n));res.ensure(n);return res;}FormalPowerSeries cut_copy(int l, int r) const {if (l >= size()) return FormalPowerSeries(r - l, 0);FormalPowerSeries res(this->begin() + l, this->begin() + std::min(size(), r));res.ensure(r - l);return res;}/* Unary Operations */FormalPowerSeries operator+() const { return *this; }FormalPowerSeries operator-() const {FormalPowerSeries res = *this;for (auto& e : res) e = -e;return res;}FormalPowerSeries& operator++() { return ++safe_get(0), * this; }FormalPowerSeries& operator--() { return --safe_get(0), * this; }FormalPowerSeries operator++(int) {FormalPowerSeries res = *this;++(*this);return res;}FormalPowerSeries operator--(int) {FormalPowerSeries res = *this;--(*this);return res;}/* Binary Operations With Constant */FormalPowerSeries& operator+=(const value_type& x) { return safe_get(0) += x, *this; }FormalPowerSeries& operator-=(const value_type& x) { return safe_get(0) -= x, *this; }FormalPowerSeries& operator*=(const value_type& x) {for (auto& e : *this) e *= x;return *this;}FormalPowerSeries& operator/=(const value_type& x) { return *this *= x.inv(); }friend FormalPowerSeries operator+(FormalPowerSeries f, const value_type& x) { f += x; return f; }friend FormalPowerSeries operator+(const value_type& x, FormalPowerSeries f) { f += x; return f; }friend FormalPowerSeries operator-(FormalPowerSeries f, const value_type& x) { f -= x; return f; }friend FormalPowerSeries operator-(const value_type& x, FormalPowerSeries f) { f -= x; return -f; }friend FormalPowerSeries operator*(FormalPowerSeries f, const value_type& x) { f *= x; return f; }friend FormalPowerSeries operator*(const value_type& x, FormalPowerSeries f) { f *= x; return f; }friend FormalPowerSeries operator/(FormalPowerSeries f, const value_type& x) { f /= x; return f; }/* Binary Operations With Formal Power Series */FormalPowerSeries& operator+=(const FormalPowerSeries& g) {const int n = g.size();ensure(n);for (int i = 0; i < n; ++i) (*this)[i] += g[i];return *this;}FormalPowerSeries& operator-=(const FormalPowerSeries& g) {const int n = g.size();ensure(n);for (int i = 0; i < n; ++i) (*this)[i] -= g[i];return *this;}FormalPowerSeries& operator*=(const FormalPowerSeries& g) { return *this = *this * g; }FormalPowerSeries& operator/=(const FormalPowerSeries& g) { return *this = *this / g; }FormalPowerSeries& operator%=(const FormalPowerSeries& g) { return *this = *this % g; }friend FormalPowerSeries operator+(FormalPowerSeries f, const FormalPowerSeries& g) { f += g; return f; }friend FormalPowerSeries operator-(FormalPowerSeries f, const FormalPowerSeries& g) { f -= g; return f; }friend FormalPowerSeries operator*(const FormalPowerSeries& f, const FormalPowerSeries& g) {const int siz_f = f.size(), siz_g = g.size();if (siz_f < siz_g) return g * f;if (std::min(siz_f, siz_g) <= 60) return atcoder::convolution(f, g);const int deg = siz_f + siz_g - 2;int fpow2 = 1;while ((fpow2 << 1) <= deg) fpow2 <<= 1;if (const int dif = deg - fpow2 + 1; dif <= 10) {FormalPowerSeries h = atcoder::convolution(std::vector<mint>(f.begin(), f.end() - dif), g);h.resize(h.size() + dif);for (int i = siz_f - dif; i < siz_f; ++i) for (int j = 0; j < siz_g; ++j) {h[i + j] += f[i] * g[j];}return h;}return atcoder::convolution(f, g);}friend FormalPowerSeries operator/(FormalPowerSeries f, FormalPowerSeries g) {if (f.size() < 60) return FPSNaive<mint>(f).div_mod(g).first;f.cut_trailing_zeros(), g.cut_trailing_zeros();const int fd = f.deg(), gd = g.deg();assert(gd >= 0);if (fd < gd) return {};if (gd == 0) {f /= g[0];return f;}std::reverse(f.begin(), f.end()), std::reverse(g.begin(), g.end());const int qd = fd - gd;f.cut(qd + 1);FormalPowerSeries q = f * g.inv(qd + 1);q.cut(qd + 1);std::reverse(q.begin(), q.end());return q;}friend FormalPowerSeries operator%(const FormalPowerSeries& f, const FormalPowerSeries& g) { return f.div_mod(g).second; }std::pair<FormalPowerSeries, FormalPowerSeries> div_mod(const FormalPowerSeries& g) const {if (size() < 60) {auto [q, r] = FPSNaive<mint>(*this).div_mod(g);return { q, r };}FormalPowerSeries q = *this / g, r = *this - g * q;r.cut_trailing_zeros();return { q, r };}/* Shift Operations */FormalPowerSeries& operator<<=(const int shamt) {return this->insert(this->begin(), shamt, 0), * this;}FormalPowerSeries& operator>>=(const int shamt) {return this->erase(this->begin(), this->begin() + std::min(shamt, size())), * this;}friend FormalPowerSeries operator<<(FormalPowerSeries f, const int shamt) { f <<= shamt; return f; }friend FormalPowerSeries operator>>(FormalPowerSeries f, const int shamt) { f >>= shamt; return f; }/* Compare */friend bool operator==(const FormalPowerSeries& f, const FormalPowerSeries& g) {const int n = f.size(), m = g.size();if (n < m) return g == f;for (int i = 0; i < m; ++i) if (f[i] != g[i]) return false;for (int i = m; i < n; ++i) if (f[i] != 0) return false;return true;}friend bool operator!=(const FormalPowerSeries& f, const FormalPowerSeries& g) { return not (f == g); }/* Other Operations */FormalPowerSeries& diff_inplace() {if (this->empty()) return *this;const int n = size();for (int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i;return (*this)[n - 1] = 0, *this;}FormalPowerSeries diff() const {FormalPowerSeries res = *this;res.diff_inplace();return res;}FormalPowerSeries& intg_inplace() {const int n = size();inv_mods<value_type> invs(n);this->resize(n + 1);for (int i = n; i > 0; --i) (*this)[i] = (*this)[i - 1] * invs[i];return (*this)[0] = 0, *this;}FormalPowerSeries intg() const {FormalPowerSeries res = *this;res.intg_inplace();return res;}FormalPowerSeries& inv_inplace(int n = -1) { return *this = inv(n); }// reference: https://opt-cp.com/fps-fast-algorithms/FormalPowerSeries inv(int n = -1) const {if (n < 0) n = size();if (n < 60) return FPSNaive<mint>(cut_copy(n)).inv();if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return inv_sparse(std::move(*sp_f), n);FormalPowerSeries f_fft, g_fft;FormalPowerSeries g{ (*this)[0].inv() };for (int k = 1; k < n; k *= 2) {f_fft = cut_copy(2 * k), g_fft = g.cut_copy(2 * k);atcoder::internal::butterfly(f_fft);atcoder::internal::butterfly(g_fft);update_inv(k, f_fft, g_fft, g);}g.resize(n);return g;}FormalPowerSeries& log_inplace(int n = -1) { return *this = log(n); }FormalPowerSeries log(int n = -1) const {assert(safe_get(0) == 1);if (n < 0) n = size();if (n < 60) return FPSNaive<mint>(cut_copy(n)).log();if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return log_sparse(std::move(*sp_f), n);FormalPowerSeries res = inv(n) * diff();res.resize(n - 1);return res.intg();}FormalPowerSeries& exp_inplace(int n = -1) { return *this = exp(n); }// https://arxiv.org/pdf/1301.5804.pdfFormalPowerSeries exp(int n = -1) const {assert(safe_get(0) == 0);if (n < 0) n = size();if (n < 60) return FPSNaive<mint>(cut_copy(n)).exp();if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return exp_sparse(std::move(*sp_f), n);// h = *this// f = exp(h) mod x ^ k// g = f^{-1} mod x ^ kFormalPowerSeries dh = diff();FormalPowerSeries f{ 1 }, f_fft;FormalPowerSeries g{ 1 }, g_fft;for (int k = 1; k < n; k *= 2) {f_fft = f.cut_copy(2 * k), atcoder::internal::butterfly(f_fft);if (k > 1) update_inv(k / 2, f_fft, g_fft, g);FormalPowerSeries t = f.cut_copy(k);t.diff_inplace();{FormalPowerSeries r = dh.cut_copy(k);r.back() = 0;atcoder::internal::butterfly(r);for (int i = 0; i < k; ++i) r[i] *= f_fft[i];atcoder::internal::butterfly_inv(r);r /= -k;t += r;t <<= 1, t[0] = t[k], t.pop_back();}t.resize(2 * k);atcoder::internal::butterfly(t);g_fft = g.cut_copy(2 * k);atcoder::internal::butterfly(g_fft);for (int i = 0; i < 2 * k; ++i) t[i] *= g_fft[i];atcoder::internal::butterfly_inv(t);t.resize(k);t /= 2 * k;FormalPowerSeries v = cut_copy(2 * k) >>= k;t <<= k - 1;t.intg_inplace();for (int i = 0; i < k; ++i) v[i] -= t[k + i];v.resize(2 * k);atcoder::internal::butterfly(v);for (int i = 0; i < 2 * k; ++i) v[i] *= f_fft[i];atcoder::internal::butterfly_inv(v);v.resize(k);v /= 2 * k;f.resize(2 * k);for (int i = 0; i < k; ++i) f[k + i] = v[i];}f.cut(n);return f;}FormalPowerSeries& pow_inplace(long long k, int n = -1) { return *this = pow(k, n); }FormalPowerSeries pow(const long long k, int n = -1) const {if (n < 0) n = size();if (n < 60) return FPSNaive<mint>(cut_copy(n)).pow(k);if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return pow_sparse(std::move(*sp_f), k, n);if (k == 0) {FormalPowerSeries f{ 1 };f.resize(n);return f;}int tlz = 0;while (tlz < size() and (*this)[tlz] == 0) ++tlz;if (tlz == size() or tlz > (n - 1) / k) return FormalPowerSeries(n, 0);const int m = n - tlz * k;FormalPowerSeries f = *this >> tlz;value_type base = f[0];return ((((f /= base).log(m) *= k).exp(m) *= base.pow(k)) <<= (tlz * k));}std::optional<FormalPowerSeries> safe_sqrt(int n = -1) const {if (n < 0) n = size();if (n < 60) return FPSNaive<mint>(cut_copy(n)).safe_sqrt();if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return safe_sqrt_sparse(std::move(*sp_f), n);int tlz = 0;while (tlz < size() and (*this)[tlz] == 0) ++tlz;if (tlz == size()) return FormalPowerSeries(n, 0);if (tlz & 1) return std::nullopt;const int m = n - tlz / 2;FormalPowerSeries h(this->begin() + tlz, this->end());auto q0 = ::safe_sqrt(h[0]);if (not q0.has_value()) return std::nullopt;FormalPowerSeries f{ *q0 }, f_fft, g{ q0->inv() }, g_fft;for (int k = 1; k < m; k *= 2) {f_fft = f.cut_copy(2 * k), atcoder::internal::butterfly(f_fft);if (k > 1) update_inv(k / 2, f_fft, g_fft, g);g_fft = g.cut_copy(2 * k);atcoder::internal::butterfly(g_fft);FormalPowerSeries h_fft = h.cut_copy(2 * k);atcoder::internal::butterfly(h_fft);for (int i = 0; i < 2 * k; ++i) h_fft[i] = (h_fft[i] - f_fft[i] * f_fft[i]) * g_fft[i];atcoder::internal::butterfly_inv(h_fft);f.resize(2 * k);const value_type iz = value_type(4 * k).inv();for (int i = 0; i < k; ++i) f[k + i] = h_fft[k + i] * iz;}f.resize(m), f <<= (tlz / 2);return f;}FormalPowerSeries& sqrt_inplace(int n = -1) { return *this = sqrt(n); }FormalPowerSeries sqrt(int n = -1) const {return *safe_sqrt(n);}value_type eval(value_type x) const {value_type y = 0;for (int i = size() - 1; i >= 0; --i) y = y * x + (*this)[i];return y;}static FormalPowerSeries prod(const std::vector<FormalPowerSeries>& fs) {if (fs.empty()) return { 1 };std::deque<FormalPowerSeries> dq(fs.begin(), fs.end());std::sort(dq.begin(), dq.end(), [](auto& f, auto& g) { return f.size() < g.size(); });while (dq.size() >= 2) {dq.push_back(dq[0] * dq[1]);dq.pop_front();dq.pop_front();}return dq.front();}std::optional<std::vector<std::pair<int, value_type>>> sparse_fps_format(int max_size) const {std::vector<std::pair<int, value_type>> res;for (int i = 0; i <= deg() and int(res.size()) <= max_size; ++i) if (value_type v = (*this)[i]; v != 0) res.emplace_back(i, v);if (int(res.size()) > max_size) return std::nullopt;return res;}private:static void update_inv(const int k, FormalPowerSeries& f_fft, FormalPowerSeries& g_fft, FormalPowerSeries& g) {FormalPowerSeries fg(2 * k);for (int i = 0; i < 2 * k; ++i) fg[i] = f_fft[i] * g_fft[i];atcoder::internal::butterfly_inv(fg);fg >>= k, fg.resize(2 * k);atcoder::internal::butterfly(fg);for (int i = 0; i < 2 * k; ++i) fg[i] *= g_fft[i];atcoder::internal::butterfly_inv(fg);const value_type iz = value_type(2 * k).inv(), c = -iz * iz;g.resize(2 * k);for (int i = 0; i < k; ++i) g[k + i] = fg[i] * c;}static FormalPowerSeries div_fps_sparse(const FormalPowerSeries& f, const std::vector<std::pair<int, value_type>>& g, int n) {const int siz = g.size();assert(siz and g[0].first == 0);const value_type inv_g0 = g[0].second.inv();FormalPowerSeries h(n);for (int i = 0; i < n; ++i) {value_type v = f.safe_get(i);for (int idx = 1; idx < siz; ++idx) {const auto& [j, gj] = g[idx];if (j > i) break;v -= gj * h[i - j];}h[i] = v * inv_g0;}return h;}static FormalPowerSeries inv_sparse(const std::vector<std::pair<int, value_type>>& g, const int n) {return div_fps_sparse(FormalPowerSeries{ 1 }, g, n);}static FormalPowerSeries exp_sparse(const std::vector<std::pair<int, value_type>>& f, const int n) {const int siz = f.size();assert(not siz or f[0].first != 0);FormalPowerSeries g(n);g[0] = 1;inv_mods<value_type> invs(n);for (int i = 1; i < n; ++i) {value_type v = 0;for (const auto& [j, fj] : f) {if (j > i) break;v += j * fj * g[i - j];}v *= invs[i];g[i] = v;}return g;}static FormalPowerSeries log_sparse(const std::vector<std::pair<int, value_type>>& f, const int n) {const int siz = f.size();assert(siz and f[0].first == 0 and f[0].second == 1);FormalPowerSeries g(n);for (int idx = 1; idx < siz; ++idx) {const auto& [j, fj] = f[idx];if (j >= n) break;g[j] = j * fj;}inv_mods<value_type> invs(n);for (int i = 1; i < n; ++i) {value_type v = g[i];for (int idx = 1; idx < siz; ++idx) {const auto& [j, fj] = f[idx];if (j > i) break;v -= fj * g[i - j] * (i - j);}v *= invs[i];g[i] = v;}return g;}static FormalPowerSeries pow_sparse(const std::vector<std::pair<int, value_type>>& f, const long long k, const int n) {if (k == 0) {FormalPowerSeries res(n, 0);res[0] = 1;return res;}const int siz = f.size();if (not siz) return FormalPowerSeries(n, 0);const int p = f[0].first;if (p > (n - 1) / k) return FormalPowerSeries(n, 0);const value_type inv_f0 = f[0].second.inv();const int lz = p * k;FormalPowerSeries g(n);g[lz] = f[0].second.pow(k);inv_mods<value_type> invs(n);for (int i = 1; lz + i < n; ++i) {value_type v = 0;for (int idx = 1; idx < siz; ++idx) {auto [j, fj] = f[idx];j -= p;if (j > i) break;v += fj * g[lz + i - j] * (value_type(k) * j - (i - j));}v *= invs[i] * inv_f0;g[lz + i] = v;}return g;}static std::optional<FormalPowerSeries> safe_sqrt_sparse(const std::vector<std::pair<int, value_type>>& f, const int n) {const int siz = f.size();if (not siz) return FormalPowerSeries(n, 0);const int p = f[0].first;if (p % 2 == 1) return std::nullopt;if (p / 2 >= n) return FormalPowerSeries(n, 0);const value_type inv_f0 = f[0].second.inv();const int lz = p / 2;FormalPowerSeries g(n);auto opt_g0 = ::safe_sqrt(f[0].second);if (not opt_g0.has_value()) return std::nullopt;g[lz] = *opt_g0;value_type k = mint(2).inv();inv_mods<value_type> invs(n);for (int i = 1; lz + i < n; ++i) {value_type v = 0;for (int idx = 1; idx < siz; ++idx) {auto [j, fj] = f[idx];j -= p;if (j > i) break;v += fj * g[lz + i - j] * (k * j - (i - j));}v *= invs[i] * inv_f0;g[lz + i] = v;}return g;}static FormalPowerSeries sqrt_sparse(const std::vector<std::pair<int, value_type>>& f, const int n) {return *safe_sqrt(f, n);}};} // namespace suisentemplate <typename mint>suisen::FormalPowerSeries<mint> sqrt(suisen::FormalPowerSeries<mint> a) {return a.sqrt();}template <typename mint>suisen::FormalPowerSeries<mint> log(suisen::FormalPowerSeries<mint> a) {return a.log();}template <typename mint>suisen::FormalPowerSeries<mint> exp(suisen::FormalPowerSeries<mint> a) {return a.exp();}template <typename mint, typename T>suisen::FormalPowerSeries<mint> pow(suisen::FormalPowerSeries<mint> a, T b) {return a.pow(b);}template <typename mint>suisen::FormalPowerSeries<mint> inv(suisen::FormalPowerSeries<mint> a) {return a.inv();}namespace suisen {template <typename T, typename U = T>struct factorial {factorial() = default;factorial(int n) { ensure(n); }static void ensure(const int n) {int sz = _fac.size();if (n + 1 <= sz) return;int new_size = std::max(n + 1, sz * 2);_fac.resize(new_size), _fac_inv.resize(new_size);for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i;_fac_inv[new_size - 1] = U(1) / _fac[new_size - 1];for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i;}T fac(const int i) {ensure(i);return _fac[i];}T operator()(int i) {return fac(i);}U fac_inv(const int i) {ensure(i);return _fac_inv[i];}U binom(const int n, const int r) {if (n < 0 or r < 0 or n < r) return 0;ensure(n);return _fac[n] * _fac_inv[r] * _fac_inv[n - r];}U perm(const int n, const int r) {if (n < 0 or r < 0 or n < r) return 0;ensure(n);return _fac[n] * _fac_inv[n - r];}private:static std::vector<T> _fac;static std::vector<U> _fac_inv;};template <typename T, typename U>std::vector<T> factorial<T, U>::_fac{ 1 };template <typename T, typename U>std::vector<U> factorial<T, U>::_fac_inv{ 1 };} // namespace suisenusing fps = FormalPowerSeries<mint>;int main() {int n, m;read(n, m);factorial<mint> fac(m);fps sm;REP(i, m + 1) REP(j, m - i + 1) {const int k = m - (i + j);const int wp = (2 * j + k) % 3;// (i + jw + kw^2) ^ nauto mul = [](fps f, fps g) {f *= g;fps h(3);REP(i, int(f.size())) h[i % 3] += f[i];return h;};fps p{ 1 };p <<= wp;fps f{ i, j, k };for (int b = n; b; b >>= 1) {if (b & 1) p = mul(p, f);f = mul(f, f);}sm += p * fac.fac(m) * fac.fac_inv(i) * fac.fac_inv(j) * fac.fac_inv(k);}mint ans = sm[0] - sm[1];ans /= mint(3).pow(m);print(ans);}