#include <chrono>
#include <ostream>
#include <numeric>
#include <iomanip>
#include <deque>
#include <unordered_set>
#include <array>
#include <utility>
#include <optional>
#include <fstream>
#include <istream>
#include <set>
#include <type_traits>
#include <iterator>
#include <vector>
#include <cassert>
#include <algorithm>
#include <queue>
#include <functional>
#include <stack>
#include <random>
#include <map>
#include <string>
#include <bitset>
#include <iostream>
#include <unordered_map>

#ifndef KK2_TEMPLATE_PROCON_HPP
#define KK2_TEMPLATE_PROCON_HPP 1


#ifndef KK2_TEMPLATE_CONSTANT_HPP
#define KK2_TEMPLATE_CONSTANT_HPP 1

#ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP
#define KK2_TEMPLATE_TYPE_ALIAS_HPP 1


using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;

using pi = std::pair<int, int>;
using pl = std::pair<i64, i64>;
using pil = std::pair<int, i64>;
using pli = std::pair<i64, int>;

template <class T> using vc = std::vector<T>;
template <class T> using vvc = std::vector<vc<T>>;
template <class T> using vvvc = std::vector<vvc<T>>;
template <class T> using vvvvc = std::vector<vvvc<T>>;

template <class T> using pq = std::priority_queue<T>;
template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#endif // KK2_TEMPLATE_TYPE_ALIAS_HPP

template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = (1 << 30) - 123;
template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);
template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);
template <> constexpr u32 infty<u32> = infty<int>;
template <> constexpr u64 infty<u64> = infty<i64>;
template <> constexpr u128 infty<u128> = infty<i128>;
template <> constexpr double infty<double> = infty<i64>;
template <> constexpr long double infty<long double> = infty<i64>;

constexpr int mod = 998244353;
constexpr int modu = 1e9 + 7;
constexpr long double PI = 3.14159265358979323846;

#endif // KK2_TEMPLATE_CONSTANT_HPP
#ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP
#define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1


#ifndef KK2_MATH_MONOID_MAX_HPP
#define KK2_MATH_MONOID_MAX_HPP 1


#ifndef KK2_TYPE_TRAITS_IO_HPP
#define KK2_TYPE_TRAITS_IO_HPP 1



namespace kk2 {

namespace type_traits {

struct istream_tag {};
struct ostream_tag {};

} // namespace type_traits

template <typename T> using is_standard_istream =
    typename std::conditional<std::is_same<T, std::istream>::value
                                  || std::is_same<T, std::ifstream>::value,
                              std::true_type,
                              std::false_type>::type;
template <typename T> using is_standard_ostream =
    typename std::conditional<std::is_same<T, std::ostream>::value
                                  || std::is_same<T, std::ofstream>::value,
                              std::true_type,
                              std::false_type>::type;
template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;
template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;

template <typename T> using is_istream =
    typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_ostream =
    typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;
template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;

} // namespace kk2

#endif // KK2_TYPE_TRAITS_IO_HPP

namespace kk2 {

namespace monoid {

template <class S, class Compare = std::less<S>> struct Max {
    static constexpr bool commutative = true;
    using M = Max;
    S a;
    bool is_unit;

    Max() : a(S()), is_unit(true) {}
    Max(S a_) : a(a_), is_unit(false) {}
    operator S() const { return a; }

    inline static M op(M l, M r) {
        if (l.is_unit or r.is_unit) return l.is_unit ? r : l;
        return Compare{}(l.a, r.a) ? r : l;
    }

    inline static M unit() { return M(); }

    bool operator==(const M &rhs) const {
        return is_unit == rhs.is_unit and (is_unit or a == rhs.a);
    }

    bool operator!=(const M &rhs) const {
        return is_unit != rhs.is_unit or (!is_unit and a != rhs.a);
    }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const M &x) {
        if (x.is_unit) os << "-inf";
        else os << x.a;
        return os;
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, M &x) {
        is >> x.a;
        x.is_unit = false;
        return is;
    }
};

} // namespace monoid

} // namespace kk2

#endif // MATH_MONOID_MAX_HPP
#ifndef KK2_MATH_MONOID_MIN_HPP
#define KK2_MATH_MONOID_MIN_HPP 1



namespace kk2 {

namespace monoid {

template <class S, class Compare = std::less<S>> struct Min {
    static constexpr bool commutative = true;
    using M = Min;
    S a;
    bool is_unit;

    Min() : a(S()), is_unit(true) {}
    Min(S a_) : a(a_), is_unit(false) {}
    operator S() const { return a; }

    inline static M op(M l, M r) {
        if (l.is_unit or r.is_unit) return l.is_unit ? r : l;
        return Compare{}(l.a, r.a) ? l : r;
    }

    inline static M unit() { return M(); }

    bool operator==(const M &rhs) const {
        return is_unit == rhs.is_unit and (is_unit or a == rhs.a);
    }

    bool operator!=(const M &rhs) const {
        return is_unit != rhs.is_unit or (!is_unit and a != rhs.a);
    }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const M &x) {
        if (x.is_unit) os << "inf";
        else os << x.a;
        return os;
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, M &x) {
        is >> x.a;
        x.is_unit = false;
        return is;
    }
};

} // namespace monoid

} // namespace kk2

#endif // KK2_MATH_MONOID_MIN_HPP
#ifndef KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP
#define KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP 1



namespace kk2 {

template <typename T> struct is_vector : std::false_type {};
template <typename T, typename Alloc> struct is_vector<std::vector<T, Alloc>> : std::true_type {};

} // namespace kk2

#endif // KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP

namespace kk2 {

template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {
    if constexpr (sizeof...(sizes) == 0) {
        return std::vector<T>(first);
    } else {
        return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...));
    }
}

template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {
    if constexpr (is_vector<T>::value) {
        for (auto &u : v) fill_all(u, x);
    } else {
        std::fill(v.begin(), v.end(), T(x));
    }
}

template <class T, class U> int iota_all(std::vector<T> &v, U x, int offset = 0) {
    if constexpr (is_vector<T>::value) {
        for (auto &u : v) offset += iota_all(u, x + offset);
    } else {
        for (auto &u : v) u = x++, ++offset;
    }
    return offset;
}

template <class C> int mysize(const C &c) { return size(c); }


// T: commutative monoid, F: (U, T) -> U
template <class U, class T, class F>
U all_monoid_prod(const std::vector<T> &v, U unit, const F &f) {
    U res = unit;
    if constexpr (is_vector<T>::value) {
        for (const auto &x : v) res = f(res, all_monoid_prod(x, unit, f));
    } else {
        for (const auto &x : v) res = f(res, x);
    }
    return res;
}

template <class U, class T> U all_sum(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a + b; });
}
template <class U, class T> U all_prod(const std::vector<T> &v, U unit = U(1)) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a * b; });
}
template <class U, class T> U all_xor(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a ^ b; });
}
template <class U, class T> U all_and(const std::vector<T> &v, U unit = U(-1)) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a & b; });
}
template <class U, class T> U all_or(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a | b; });
}
template <class U, class T> U all_min(const std::vector<T> &v) {
    return all_monoid_prod<monoid::Min<U>, T>(v, monoid::Min<U>::unit(), monoid::Min<U>::op);
}
template <class U, class T> U all_max(const std::vector<T> &v) {
    return all_monoid_prod<monoid::Max<U>, T>(v, monoid::Max<U>::unit(), monoid::Max<U>::op);
}
template <class U, class T> U all_gcd(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::gcd(a, b); });
}
template <class U, class T> U all_lcm(const std::vector<T> &v, U unit = U(1)) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::lcm(a, b); });
}

} // namespace kk2

#endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP
#ifndef KK2_TEMPLATE_IO_UTIL_HPP
#define KK2_TEMPLATE_IO_UTIL_HPP 1



// なんかoj verifyはプロトタイプ宣言が落ちる

namespace impl {

struct read {
    template <class IStream, class T> inline static void all_read(IStream &is, T &x) { is >> x; }

    template <class IStream, class T, class U>
    inline static void all_read(IStream &is, std::pair<T, U> &p) {
        all_read(is, p.first);
        all_read(is, p.second);
    }

    template <class IStream, class T> inline static void all_read(IStream &is, std::vector<T> &v) {
        for (T &x : v) all_read(is, x);
    }

    template <class IStream, class T, size_t F>
    inline static void all_read(IStream &is, std::array<T, F> &a) {
        for (T &x : a) all_read(is, x);
    }
};

struct write {
    template <class OStream, class T> inline static void all_write(OStream &os, const T &x) {
        os << x;
    }

    template <class OStream, class T, class U>
    inline static void all_write(OStream &os, const std::pair<T, U> &p) {
        all_write(os, p.first);
        all_write(os, ' ');
        all_write(os, p.second);
    }

    template <class OStream, class T>
    inline static void all_write(OStream &os, const std::vector<T> &v) {
        for (int i = 0; i < (int)v.size(); ++i) {
            if (i) all_write(os, ' ');
            all_write(os, v[i]);
        }
    }

    template <class OStream, class T, size_t F>
    inline static void all_write(OStream &os, const std::array<T, F> &a) {
        for (int i = 0; i < (int)F; ++i) {
            if (i) all_write(os, ' ');
            all_write(os, a[i]);
        }
    }
};

} // namespace impl

template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::pair<T, U> &p) {
    impl::read::all_read(is, p);
    return is;
}

template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::vector<T> &v) {
    impl::read::all_read(is, v);
    return is;
}

template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::array<T, F> &a) {
    impl::read::all_read(is, a);
    return is;
}

template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::pair<T, U> &p) {
    impl::write::all_write(os, p);
    return os;
}

template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::vector<T> &v) {
    impl::write::all_write(os, v);
    return os;
}

template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::array<T, F> &a) {
    impl::write::all_write(os, a);
    return os;
}

#endif // KK2_TEMPLATE_IO_UTIL_HPP
#ifndef KK2_TEMPLATE_MACROS_HPP
#define KK2_TEMPLATE_MACROS_HPP 1

#define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_)
#define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i)
#define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i)
#define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i)
#define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)

#define fi first
#define se second
#define all(p) begin(p), end(p)

#endif // KK2_TEMPLATE_MACROS_HPP

struct FastIOSetUp {
    FastIOSetUp() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} fast_io_set_up;

auto &kin = std::cin;
auto &kout = std::cout;
auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;

void Yes(bool b = 1) { kout << (b ? "Yes\n" : "No\n"); }
void No(bool b = 1) { kout << (b ? "No\n" : "Yes\n"); }
void YES(bool b = 1) { kout << (b ? "YES\n" : "NO\n"); }
void NO(bool b = 1) { kout << (b ? "NO\n" : "YES\n"); }
void yes(bool b = 1) { kout << (b ? "yes\n" : "no\n"); }
void no(bool b = 1) { kout << (b ? "no\n" : "yes\n"); }
template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }

std::istream &operator>>(std::istream &is, u128 &x) {
    std::string s;
    is >> s;
    x = 0;
    for (char c : s) {
        assert('0' <= c && c <= '9');
        x = x * 10 + c - '0';
    }
    return is;
}

std::istream &operator>>(std::istream &is, i128 &x) {
    std::string s;
    is >> s;
    bool neg = s[0] == '-';
    x = 0;
    for (int i = neg; i < (int)s.size(); i++) {
        assert('0' <= s[i] && s[i] <= '9');
        x = x * 10 + s[i] - '0';
    }
    if (neg) x = -x;
    return is;
}

std::ostream &operator<<(std::ostream &os, u128 x) {
    if (x == 0) return os << '0';
    std::string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

std::ostream &operator<<(std::ostream &os, i128 x) {
    if (x == 0) return os << '0';
    if (x < 0) {
        os << '-';
        x = -x;
    }
    std::string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

#endif // KK2_TEMPLATE_PROCON_HPP
#ifndef KK2_TEMPLATE_DEBUG_HPP
#define KK2_TEMPLATE_DEBUG_HPP 1


#ifndef KK2_TYPE_TRAITS_MEMBER_HPP
#define KK2_TYPE_TRAITS_MEMBER_HPP 1



namespace kk2 {

#define HAS_MEMBER_FUNC(member)                                                                    \
    template <typename T, typename... Ts> struct has_member_func_##member##_impl {                 \
        template <typename U>                                                                      \
        static std::true_type check(decltype(std::declval<U>().member(std::declval<Ts>()...)) *);  \
        template <typename U> static std::false_type check(...);                                   \
        using type = decltype(check<T>(nullptr));                                                  \
    };                                                                                             \
    template <typename T, typename... Ts> struct has_member_func_##member                          \
        : has_member_func_##member##_impl<T, Ts...>::type {};                                      \
    template <typename T, typename... Ts> using has_member_func_##member##_t =                     \
        std::enable_if_t<has_member_func_##member<T, Ts...>::value>;                               \
    template <typename T, typename... Ts> using not_has_member_func_##member##_t =                 \
        std::enable_if_t<!has_member_func_##member<T, Ts...>::value>;

#define HAS_MEMBER_VAR(member)                                                                     \
    template <typename T> struct has_member_var_##member##_impl {                                  \
        template <typename U> static std::true_type check(decltype(std::declval<U>().member) *);   \
        template <typename U> static std::false_type check(...);                                   \
        using type = decltype(check<T>(nullptr));                                                  \
    };                                                                                             \
    template <typename T> struct has_member_var_##member                                           \
        : has_member_var_##member##_impl<T>::type {};                                              \
    template <typename T> using has_member_var_##member##_t =                                      \
        std::enable_if_t<has_member_var_##member<T>::value>;                                       \
    template <typename T> using not_has_member_var_##member##_t =                                  \
        std::enable_if_t<!has_member_var_##member<T>::value>;

HAS_MEMBER_FUNC(debug_output)
HAS_MEMBER_FUNC(val)


#undef HAS_MEMBER_FUNC
#undef HAS_MEMBER_VAR
} // namespace kk2

#endif // KK2_TYPE_TRAITS_MEMBER_HPP

namespace kk2 {

namespace debug {

#ifdef KK2

template <class OStream, is_ostream_t<OStream> *> void output(OStream &os);
template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const T &t);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::vector<T> &v);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::vector<std::vector<T>> &d);
template <class OStream, class T, size_t F, is_ostream_t<OStream> *>
void output(OStream &os, const std::array<T, F> &a);
template <class OStream, class T, class U, is_ostream_t<OStream> *>
void output(OStream &os, const std::pair<T, U> &p);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::queue<T> &q);
template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> *>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::deque<T> &d);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::stack<T> &s);
template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s);
template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s);
template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s);
template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s);
template <class OStream,
          class Key,
          class T,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m);
template <class OStream,
          class Key,
          class T,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m);
template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &) {}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t) {
    if constexpr (has_member_func_debug_output<T, OStream &>::value) {
        t.debug_output(os);
    } else {
        os << t;
    }
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::vector<T> &v) {
    os << "[";
    for (int i = 0; i < (int)v.size(); i++) {
        output(os, v[i]);
        if (i + 1 != (int)v.size()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::vector<std::vector<T>> &d) {
    os << "[\n";
    for (int i = 0; i < (int)d.size(); i++) {
        output(os, d[i]);
        output(os, "\n");
    }
    os << "]";
}

template <class OStream, class T, size_t F, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::array<T, F> &a) {
    os << "[";
    for (int i = 0; i < (int)F; i++) {
        output(os, a[i]);
        if (i + 1 != (int)F) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, class U, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::pair<T, U> &p) {
    os << "(";
    output(os, p.first);
    os << ", ";
    output(os, p.second);
    os << ")";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::queue<T> &q) {
    os << "[";
    std::queue<T> tmp = q;
    while (!tmp.empty()) {
        output(os, tmp.front());
        tmp.pop();
        if (!tmp.empty()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q) {
    os << "[";
    std::priority_queue<T, Container, Compare> tmp = q;
    while (!tmp.empty()) {
        output(os, tmp.top());
        tmp.pop();
        if (!tmp.empty()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::deque<T> &d) {
    os << "[";
    std::deque<T> tmp = d;
    while (!tmp.empty()) {
        output(os, tmp.front());
        tmp.pop_front();
        if (!tmp.empty()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::stack<T> &s) {
    os << "[";
    std::stack<T> tmp = s;
    std::vector<T> v;
    while (!tmp.empty()) {
        v.push_back(tmp.top());
        tmp.pop();
    }
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        output(os, v[i]);
        if (i != 0) os << ", ";
    }
    os << "]";
}

template <class OStream,
          class Key,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s) {
    os << "{";
    std::set<Key, Compare, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s) {
    os << "{";
    std::multiset<Key, Compare, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s) {
    os << "{";
    std::unordered_set<Key, Hash, KeyEqual, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s) {
    os << "{";
    std::unordered_multiset<Key, Hash, KeyEqual, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class T,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m) {
    os << "{";
    std::map<Key, T, Compare, Allocator> tmp = m;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, it->first);
        os << ": ";
        output(os, it->second);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class T,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m) {
    os << "{";
    std::unordered_map<Key, T, Hash, KeyEqual, Allocator> tmp = m;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, it->first);
        os << ": ";
        output(os, it->second);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t, const Args &...args) {
    output(os, t);
    os << ' ';
    output(os, args...);
}

template <class OStream, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os) {
    os << '\n';
    os.flush();
}

template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &os, const T &t, const Args &...args) {
    output(os, t, args...);
    os << '\n';
    os.flush();
}

std::vector<std::string> sep(const char *s) {
    std::vector<std::string> res;
    std::string now;
    int dep = 0;
    while (true) {
        if (*s == '\0') {
            res.emplace_back(now);
            break;
        }
        if (*s == '(' or *s == '[' or *s == '{') dep++;
        if (*s == ')' or *s == ']' or *s == '}') dep--;
        if (dep == 0 and *s == ',') {
            res.emplace_back(now);
            now.clear();
        } else if (!isspace(*s)) {
            now += *s;
        }
        s++;
    }
    return res;
}

void show_vars(const std::vector<std::string> &, int) {}

template <class T, class... Args>
void show_vars(const std::vector<std::string> &name, int pos, const T &t, const Args &...args) {
    assert(pos < (int)name.size());
    output(std::cerr, name[pos++] + ":", t);
    if (sizeof...(args) > 0) output(std::cerr, ", ");
    show_vars(name, pos, args...);
}

#define kdebug(...)                                                                                \
    kk2::debug::output(std::cerr, "line:" + std::to_string(__LINE__));                             \
    kk2::debug::output(std::cerr, ' ');                                                            \
    kk2::debug::show_vars(kk2::debug::sep(#__VA_ARGS__), 0, __VA_ARGS__);                          \
    kk2::debug::outputln(std::cerr);

#else

template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &, const Args &...) {}

template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &, const Args &...) {}

template <class... Args> void fix_warn(const Args &...) {}

#define kdebug(...) kk2::debug::fix_warn(__VA_ARGS__);

#endif // KK2

} // namespace debug

} // namespace kk2

#endif // KK2_TEMPLATE_DEBUG_HPP
#ifndef KK2_MODINT_MODINT_HPP
#define KK2_MODINT_MODINT_HPP 1


#ifndef KK2_TYPE_TRAITS_INTERGRAL_HPP
#define KK2_TYPE_TRAITS_INTERGRAL_HPP 1



namespace kk2 {

#ifndef _MSC_VER

template <typename T> using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value
                                  or std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value
                                  or std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_integral =
    typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value
                                  or is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_signed =
    typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_unsigned =
    typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;

template <typename T> using to_unsigned =
    typename std::conditional<is_signed_int128<T>::value,
                              make_unsigned_int128<T>,
                              typename std::conditional<std::is_signed<T>::value,
                                                        std::make_unsigned<T>,
                                                        std::common_type<T>>::type>::type;

#else

template <typename T> using is_integral = std::enable_if_t<std::is_integral<T>::value>;
template <typename T> using is_signed = std::enable_if_t<std::is_signed<T>::value>;
template <typename T> using is_unsigned = std::enable_if_t<std::is_unsigned<T>::value>;
template <typename T> using to_unsigned = std::make_unsigned<T>;

#endif // _MSC_VER

template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;
template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;

} // namespace kk2

#endif // KK2_TYPE_TRAITS_INTERGRAL_HPP

namespace kk2 {

template <int p> struct ModInt {
    using mint = ModInt;

  public:
    static int Mod;

    constexpr static unsigned int getmod() {
        if (p > 0) return p;
        else return Mod;
    }

    static void setmod(int Mod_) {
        assert(1 <= Mod_);
        Mod = Mod_;
    }

    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    constexpr ModInt() : _v(0) {}

    template <class T, is_integral_t<T> * = nullptr> constexpr ModInt(T v) {
        if constexpr (is_signed<T>::value) {
            v = v % (long long)(getmod());
            if (v < 0) v += getmod();
            _v = v;
        } else if constexpr (is_unsigned<T>::value) {
            _v = v %= getmod();
        } else {
            ModInt();
        }
    }

    unsigned int val() const { return _v; }

    mint &operator++() {
        _v++;
        if (_v == getmod()) _v = 0;
        return *this;
    }

    mint &operator--() {
        if (_v == 0) _v = getmod();
        _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 >= getmod()) _v -= getmod();
        return *this;
    }

    mint &operator-=(const mint &rhs) {
        _v += getmod() - rhs._v;
        if (_v >= getmod()) _v -= getmod();
        return *this;
    }

    mint &operator*=(const mint &rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        z %= getmod();
        _v = z;
        return *this;
    }

    mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }
    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; }

    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 {
        long long s = getmod(), t = _v;
        long long m0 = 0, m1 = 1;

        while (t) {
            long long u = s / t;
            s -= t * u;
            m0 -= m1 * u;

            std::swap(s, t);
            std::swap(m0, m1);
        }
        if (m0 < 0) m0 += getmod() / s;
        return m0;
    }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const mint &mint_) {
        os << mint_._v;
        return os;
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, mint &mint_) {
        long long x;
        is >> x;
        mint_ = mint(x);
        return is;
    }

  private:
    unsigned int _v;
};

template <int p> int ModInt<p>::Mod = 998244353;

using mint998 = ModInt<998244353>;
using mint107 = ModInt<1000000007>;

} // namespace kk2

#endif // KK2_MODINT_MODINT_HPP
#ifndef KK2_MATH_PRIME_FACTORIZE_HPP
#define KK2_MATH_PRIME_FACTORIZE_HPP 1


#ifndef KK2_MATH_MOD_POW_MOD_HPP
#define KK2_MATH_MOD_POW_MOD_HPP 1


namespace kk2 {

template <class S, class T, class U> constexpr S pow_mod(T x, U n, T m) {
    assert(n >= 0);
    if (m == 1) return S(0);
    S _m = m, r = 1;
    S y = x % _m;
    if (y < 0) y += _m;
    while (n) {
        if (n & 1) r = (r * y) % _m;
        if (n >>= 1) y = (y * y) % _m;
    }
    return r;
}

} // namespace kk2

#endif // KK2_MATH_MOD_POW_MOD_HPP
#ifndef KK2_MODINT_MONT_ARB_HPP
#define KK2_MODINT_MONT_ARB_HPP 1



namespace kk2 {

template <typename Int, typename UInt, typename Long, typename ULong, int id>
struct ArbitraryLazyMontgomeryModIntBase {
    using mint = ArbitraryLazyMontgomeryModIntBase;

    inline static UInt mod;
    inline static UInt r;
    inline static UInt n2;
    static constexpr int bit_length = sizeof(UInt) * 8;

    static UInt get_r() {
        UInt ret = mod;
        while (mod * ret != 1) ret *= UInt(2) - mod * ret;
        return ret;
    }

    static void setmod(UInt m) {
        assert(m < (UInt(1u) << (bit_length - 2)));
        assert(m & 1);
        mod = m, n2 = -ULong(m) % m, r = get_r();
    }

    UInt _v;

    ArbitraryLazyMontgomeryModIntBase() : _v(0) {}

    template <class T, is_integral_t<T> * = nullptr> ArbitraryLazyMontgomeryModIntBase(const T &b)
        : _v(reduce(ULong(b % (Int)mod + mod) * n2)) {}

    static UInt reduce(const ULong &b) {
        return (b + ULong(UInt(b) * UInt(-r)) * mod) >> bit_length;
    }

    mint &operator+=(const mint &b) {
        if (Int(_v += b._v - 2 * mod) < 0) _v += 2 * mod;
        return *this;
    }

    mint &operator-=(const mint &b) {
        if (Int(_v -= b._v) < 0) _v += 2 * mod;
        return *this;
    }

    mint &operator*=(const mint &b) {
        _v = reduce(ULong(_v) * b._v);
        return *this;
    }

    mint &operator/=(const mint &b) {
        *this *= b.inv();
        return *this;
    }

    mint operator-() const { return mint(0) - mint(*this); }
    mint operator+() const { return mint(*this); }
    friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
    friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
    friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
    friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }

    bool operator==(const mint &b) const {
        return (_v >= mod ? _v - mod : _v) == (b._v >= mod ? b._v - mod : b._v);
    }

    bool operator!=(const mint &b) const {
        return (_v >= mod ? _v - mod : _v) != (b._v >= mod ? b._v - mod : b._v);
    }

    template <class T> mint pow(T n) const {
        mint ret(1), mul(*this);
        n %= (Long)getmod() - 1;
        while (n > 0) {
            if (n & 1) ret *= mul;
            if (n >>= 1) mul *= mul;
        }
        return ret;
    }

    mint inv() const {
        Int s = getmod(), t = val(), m0 = 0, m1 = 1;
        while (t) {
            Int u = s / t;
            std::swap(s -= t * u, t);
            std::swap(m0 -= m1 * u, m1);
        }
        if (m0 < 0) m0 += getmod();
        return mint(m0);
    }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const mint &x) {
        return os << x.val();
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, mint &x) {
        Long t;
        is >> t;
        x = mint(t);
        return (is);
    }

    UInt val() const {
        UInt ret = reduce(_v);
        return ret >= mod ? ret - mod : ret;
    }

    static UInt getmod() { return mod; }
};

template <int id> using ArbitraryLazyMontgomeryModInt =
    ArbitraryLazyMontgomeryModIntBase<int, unsigned int, long long, unsigned long long, id>;

template <int id> using ArbitraryLazyMontgomeryModInt64bit =
    ArbitraryLazyMontgomeryModIntBase<long long, unsigned long long, __int128_t, __uint128_t, id>;

} // namespace kk2

#endif // KK2_MODINT_MONT_ARB_HPP
#ifndef KK2_RANDOM_GEN_HPP
#define KK2_RANDOM_GEN_HPP 1


#ifndef KK2_RANDOM_SEED_HPP
#define KK2_RANDOM_SEED_HPP 1


namespace kk2 {

namespace random {

using u64 = unsigned long long;

inline u64 non_deterministic_seed() {
    u64 seed = std::chrono::duration_cast<std::chrono::nanoseconds>(
                   std::chrono::high_resolution_clock::now().time_since_epoch())
                   .count();
    seed ^= reinterpret_cast<u64>(&seed);
    seed ^= seed << 5;
    seed ^= seed >> 41;
    seed ^= seed << 20;
    return seed;
}

inline u64 deterministic_seed() { return 5801799128519729247ull; }

inline u64 seed() {
#if defined(KK2_RANDOM_DETERMINISTIC)
    return deterministic_seed();
#else
    return non_deterministic_seed();
#endif
}

} // namespace random

} // namespace kk2

#endif // KK2_RANDOM_SEED_HPP

namespace kk2 {

namespace random {

using i64 = long long;
using u64 = unsigned long long;

inline u64 rng() {
    static std::mt19937_64 mt(kk2::random::seed());
    return mt();
}

// [l, r)
inline i64 rng(i64 l, i64 r) {
    assert(l < r);
    return l + rng() % (r - l);
}

// [l, r)
template <class T> std::vector<T> random_vector(int n, T l, T r) {
    std::vector<T> res(n);
    for (int i = 0; i < n; i++) res[i] = rng(l, r);
    return res;
}

// [l, r)
std::vector<i64> distinct_rng(i64 l, i64 r, i64 n) {
    assert(l < r and n <= r - l);
    std::unordered_set<i64> st;
    for (i64 i = n; i; --i) {
        i64 m = rng(l, r + 1 - i);
        if (st.find(m) != st.end()) m = r - i;
        st.insert(m);
    }
    std::vector<i64> res(st.begin(), st.end());
    std::sort(res.begin(), res.end());
    return res;
}

template <class Iter> void shuffle(Iter first, Iter last) {
    if (first == last) return;
    int len = 1;
    for (auto it = first + 1; it != last; ++it) {
        len++;
        int j = rng(0, len);
        if (j != len - 1) std::iter_swap(first + j, it);
    }
}

template <class T> std::vector<T> perm(int n) {
    std::vector<T> res(n);
    std::iota(res.begin(), res.end(), T(0));
    shuffle(res.begin(), res.end());
    return res;
}

template <class T> std::vector<T> choices(int l, int r, int k) {
    assert(l < r and k <= r - l);
    std::vector<T> res(r - l);
    std::iota(res.begin(), res.end(), T(l));
    shuffle(res.begin(), res.end());
    res.resize(k);
    return res;
}

} // namespace random

} // namespace kk2

#endif // KK2_RANDOM_GEN_HPP
#ifndef KK2_MATH_IS_PRIME_HPP
#define KK2_MATH_IS_PRIME_HPP 1



namespace kk2 {

namespace number_theory {

template <class T, class U> bool miller_rabin(const T &n, const std::vector<T> &ws) {
    if (n <= 2) return n == 2;
    if (~n & 1) return false;

    T d = n - 1;
    while (~d & 1) d >>= 1;
    U e = 1, rev = n - 1;
    for (T w : ws) {
        if (w % n == 0) continue;
        T t = d;
        U y = pow_mod<T, T, U>(w, t, n);
        while (t != n - 1 and y != e and y != rev) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != rev and ~t & 1) return false;
    }
    return true;
}

bool miller_rabin_u64(unsigned long long n) {
    return miller_rabin<unsigned long long, __uint128_t>(
        n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}

template <class mint>
bool miller_rabin_mont(unsigned long long n, const std::vector<unsigned long long> &ws) {
    if (n <= 2) return n == 2;
    if (~n & 1) return false;

    if (mint::getmod() != n) mint::setmod(n);
    unsigned long long d = n - 1;
    while (~d & 1) d >>= 1;
    mint e = 1, rev = n - 1;
    for (unsigned long long w : ws) {
        if (w % n == 0) continue;
        unsigned long long t = d;
        mint y = mint(w).pow(t);
        while (t != n - 1 and y != e and y != rev) {
            y *= y;
            t <<= 1;
        }
        if (y != rev and ~t & 1) return false;
    }
    return true;
}

bool is_prime(unsigned long long n) {
    using mint32 = ArbitraryLazyMontgomeryModInt<54305750>;
    using mint64 = ArbitraryLazyMontgomeryModInt64bit<54305750>;

    if (n <= 2) return n == 2;
    if (~n & 1) return false;
    if (n < (1ull << 30)) {
        return miller_rabin_mont<mint32>(n, {2, 7, 61});
    } else if (n < (1ull << 62)) {
        return miller_rabin_mont<mint64>(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
    } else {
        return miller_rabin_u64(n);
    }
}

}; // namespace number_theory

using number_theory::is_prime;

}; // namespace kk2

#endif // KK2_MATH_IS_PRIME_HPP

namespace kk2 {

namespace number_theory {

using i64 = long long;
using u64 = unsigned long long;

template <class mint, class T> T pollard_rho(T n) {
    if (~n & 1) return 2;
    if (is_prime(n)) return n;
    if (mint::getmod() != n) mint::setmod(n);

    mint R, one = 1;
    auto f = [&](mint x) {
        return x * x + R;
    };
    auto _rng = [&]() {
        return kk2::random::rng(2, n);
    };
    while (true) {
        mint x, y, ys, q = one;
        R = _rng(), y = _rng();
        T g = 1;
        constexpr int m = 128;
        for (int r = 1; g == 1; r <<= 1) {
            x = y;
            for (int i = 0; i < r; i++) y = f(y);
            for (int k = 0; k < r && g == 1; k += m) {
                ys = y;
                for (int i = 0; i < std::min(m, r - k); i++) {
                    y = f(y);
                    q *= x - y;
                }
                g = std::gcd(q.val(), n);
            }
        }
        if (g == n) do {
                ys = f(ys);
                g = std::gcd((x - ys).val(), n);
            } while (g == 1);
        if (g != n) return g;
    }
    exit(1);
}

std::vector<i64> inner_factorize(i64 n) {
    using mint32 = ArbitraryLazyMontgomeryModInt<54355165>;
    using mint64 = ArbitraryLazyMontgomeryModInt64bit<54355165>;
    assert(n);
    if (n < 0) n = -n;
    if (n == 1) return {};
    u64 p;
    if (n <= (1ll << 30)) {
        p = pollard_rho<mint32, unsigned int>(n);
    } else if (n <= (1ll << 62)) {
        p = pollard_rho<mint64, unsigned long long>(n);
    } else {
        exit(1);
    }
    if (i64(p) == n) return {i64(p)};
    auto l = inner_factorize(p);
    auto r = inner_factorize(n / p);
    std::copy(r.begin(), r.end(), std::back_inserter(l));
    return l;
}

std::vector<std::pair<i64, int>> factorize(i64 n) {
    auto tmp = inner_factorize(n);
    std::sort(tmp.begin(), tmp.end());
    std::vector<std::pair<i64, int>> res;
    for (int i = 0; i < (int)tmp.size(); i++) {
        if (i == 0 or res.back().first != tmp[i]) {
            res.emplace_back(tmp[i], 1);
        } else {
            res.back().second++;
        }
    }
    return res;
}

std::map<i64, int> factorize_map(i64 n) {
    auto tmp = inner_factorize(n);
    std::map<i64, int> res;
    for (auto x : tmp) res[x]++;
    return res;
}

std::vector<i64> divisors(i64 n) {
    if (n == 0) return {};

    auto f = factorize(n);
    std::vector<i64> res = {1};
    for (auto [p, k] : f) {
        int sz = res.size();
        i64 x = 1;
        for (int i = 0; i < k; i++) {
            x *= p;
            for (int j = 0; j < sz; j++) { res.emplace_back(res[j] * x); }
        }
    }
    std::sort(res.begin(), res.end());
    return res;
}

} // namespace number_theory

using number_theory::divisors;
using number_theory::factorize;
using number_theory::factorize_map;

} // namespace kk2


#endif // KK2_MATH_PRIME_FACTORIZE_HPP
using namespace std;

void solve() {
    /*
    3K = N
    頂点K+1の根付き木T（子供に順序あり）, Tのroot以外の(子供の個数+1)の総積の総和
    dp[i] := 頂点個数iのsum
    dp[0] = 0, dp[1] = 1
    dp[i] = sum_{j=1}^{i-1} (j + 1) * sum_{sum(k)=i-1} dp[k_1] * ... * dp[k_j]
    f(X) = sum_{i} dp[i] * X^i
    f(X)(1-f(x))^2=X
    answer: [X^K](f(X) + f(X)^2 + ...) = [X^K](1-f(X))^{-1}
    定数項が単元なら，逆元を定義可能
    g(X) = (1-f(X))^{-1} - 1
    -> g(X)/(1+g(X))^3 = X
    [X^K]g(X) = 1/K * [X^{K-1}](1+x)^3K = binom(3K, K-1)/K
    */

    int n, m;
    kin >> n >> m;
    if (n % 3) {
        kout << 0 << kendl;
        return;
    }

    using mint = kk2::ModInt<0>;
    mint::setmod(m);
    int k = n / 3;

    auto pf = kk2::factorize(m);
    mint res = 1;
    vc<int> v_ps(pf.size());

    auto multiply = [&](int i, bool inv) {
        rep (j, pf.size()) {
            int p = pf[j].first;
            int v = 0;
            while (i % p == 0) {
                i /= p;
                v++;
            }
            if (inv) v_ps[j] -= v;
            else v_ps[j] += v;
        }
        if (inv) res /= mint(i);
        else res *= mint(i);
    };

    multiply(k, 1);
    rep (i, k - 1) multiply(3 * k - i, 0), multiply(k - i - 1, 1);
    rep (i, pf.size()) {
        int p = pf[i].first;
        int v = v_ps[i];
        assert(v >= 0);
        res *= mint(p).pow(v);
    }
    kout << res << kendl;
}

int main() {
    int t = 1;
    // kin >> t;
    rep (t) solve();

    return 0;
}
// Author: kk2
// converted by https://github.com/kk2a/cpp-bundle
// 2025-05-17 19:21:07