結果

問題 No.2983 Christmas Color Grid (Advent Calender ver.)
ユーザー tko919
提出日時 2024-12-08 03:45:09
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 3,340 ms
コード長 20,476 bytes
コンパイル時間 5,450 ms
コンパイル使用メモリ 318,616 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-08 03:45:17
合計ジャッジ時間 7,321 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 64
権限があれば一括ダウンロードができます

ソースコード

diff #

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())

using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template <typename T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T, typename U> T ceil(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U> T floor(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T> int popcnt(T x) {
    return __builtin_popcountll(x);
}
template <typename T> int topbit(T x) {
    return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T> int lowbit(T x) {
    return (x == 0 ? -1 : __builtin_ctzll(x));
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "P(" << p.first << ", " << p.second << ")";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
    os << "{";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if (itr != map_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T> void _show(int i, T name) {
    cerr << '\n';
}
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
    for (; a[i] != ',' && a[i] != '\0'; i++)
        cerr << a[i];
    cerr << ":" << b << " ";
    _show(i + 1, a, c...);
}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf

uint32_t pil = 0, pir = 0, por = 0;

struct Pre {
    char num[10000][4];
    constexpr Pre() : num() {
        for (int i = 0; i < 10000; i++) {
            int n = i;
            for (int j = 3; j >= 0; j--) {
                num[i][j] = n % 10 | '0';
                n /= 10;
            }
        }
    }
} constexpr pre;

inline void load() {
    memmove(ibuf, ibuf + pil, pir - pil);
    pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
    pil = 0;
    if (pir < SZ)
        ibuf[pir++] = '\n';
}

inline void flush() {
    fwrite(obuf, 1, por, stdout);
    por = 0;
}

void rd(char &c) {
    do {
        if (pil + 1 > pir)
            load();
        c = ibuf[pil++];
    } while (isspace(c));
}

void rd(string &x) {
    x.clear();
    char c;
    do {
        if (pil + 1 > pir)
            load();
        c = ibuf[pil++];
    } while (isspace(c));
    do {
        x += c;
        if (pil == pir)
            load();
        c = ibuf[pil++];
    } while (!isspace(c));
}

template <typename T> void rd_real(T &x) {
    string s;
    rd(s);
    x = stod(s);
}

template <typename T> void rd_integer(T &x) {
    if (pil + 100 > pir)
        load();
    char c;
    do
        c = ibuf[pil++];
    while (c < '-');
    bool minus = 0;
    if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
        if (c == '-') {
            minus = 1, c = ibuf[pil++];
        }
    }
    x = 0;
    while ('0' <= c) {
        x = x * 10 + (c & 15), c = ibuf[pil++];
    }
    if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
        if (minus)
            x = -x;
    }
}

void rd(int &x) {
    rd_integer(x);
}
void rd(ll &x) {
    rd_integer(x);
}
void rd(i128 &x) {
    rd_integer(x);
}
void rd(uint &x) {
    rd_integer(x);
}
void rd(ull &x) {
    rd_integer(x);
}
void rd(u128 &x) {
    rd_integer(x);
}
void rd(double &x) {
    rd_real(x);
}
void rd(long double &x) {
    rd_real(x);
}

template <class T, class U> void rd(pair<T, U> &p) {
    return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T> void rd_tuple(T &t) {
    if constexpr (N < std::tuple_size<T>::value) {
        auto &x = std::get<N>(t);
        rd(x);
        rd_tuple<N + 1>(t);
    }
}
template <class... T> void rd(tuple<T...> &tpl) {
    rd_tuple(tpl);
}

template <size_t N = 0, typename T> void rd(array<T, N> &x) {
    for (auto &d : x)
        rd(d);
}
template <class T> void rd(vector<T> &x) {
    for (auto &d : x)
        rd(d);
}

void read() {}
template <class H, class... T> void read(H &h, T &...t) {
    rd(h), read(t...);
}

void wt(const char c) {
    if (por == SZ)
        flush();
    obuf[por++] = c;
}
void wt(const string s) {
    for (char c : s)
        wt(c);
}
void wt(const char *s) {
    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++)
        wt(s[i]);
}

template <typename T> void wt_integer(T x) {
    if (por > SZ - 100)
        flush();
    if (x < 0) {
        obuf[por++] = '-', x = -x;
    }
    int outi;
    for (outi = 96; x >= 10000; outi -= 4) {
        memcpy(out + outi, pre.num[x % 10000], 4);
        x /= 10000;
    }
    if (x >= 1000) {
        memcpy(obuf + por, pre.num[x], 4);
        por += 4;
    } else if (x >= 100) {
        memcpy(obuf + por, pre.num[x] + 1, 3);
        por += 3;
    } else if (x >= 10) {
        int q = (x * 103) >> 10;
        obuf[por] = q | '0';
        obuf[por + 1] = (x - q * 10) | '0';
        por += 2;
    } else
        obuf[por++] = x | '0';
    memcpy(obuf + por, out + outi + 4, 96 - outi);
    por += 96 - outi;
}

template <typename T> void wt_real(T x) {
    ostringstream oss;
    oss << fixed << setprecision(15) << double(x);
    string s = oss.str();
    wt(s);
}

void wt(int x) {
    wt_integer(x);
}
void wt(ll x) {
    wt_integer(x);
}
void wt(i128 x) {
    wt_integer(x);
}
void wt(uint x) {
    wt_integer(x);
}
void wt(ull x) {
    wt_integer(x);
}
void wt(u128 x) {
    wt_integer(x);
}
void wt(double x) {
    wt_real(x);
}
void wt(long double x) {
    wt_real(x);
}

template <class T, class U> void wt(const pair<T, U> val) {
    wt(val.first);
    wt(' ');
    wt(val.second);
}
template <size_t N = 0, typename T> void wt_tuple(const T t) {
    if constexpr (N < std::tuple_size<T>::value) {
        if constexpr (N > 0) {
            wt(' ');
        }
        const auto x = std::get<N>(t);
        wt(x);
        wt_tuple<N + 1>(t);
    }
}
template <class... T> void wt(tuple<T...> tpl) {
    wt_tuple(tpl);
}
template <class T, size_t S> void wt(const array<T, S> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
        if (i)
            wt(' ');
        wt(val[i]);
    }
}
template <class T> void wt(const vector<T> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
        if (i)
            wt(' ');
        wt(val[i]);
    }
}

void print() {
    wt('\n');
}
template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) {
    wt(head);
    if (sizeof...(Tail))
        wt(' ');
    print(forward<Tail>(tail)...);
}
void __attribute__((destructor)) _d() {
    flush();
}
} // namespace fastio

using fastio::flush;
using fastio::print;
using fastio::read;

inline void first(bool i = true) {
    print(i ? "first" : "second");
}
inline void Alice(bool i = true) {
    print(i ? "Alice" : "Bob");
}
inline void Takahashi(bool i = true) {
    print(i ? "Takahashi" : "Aoki");
}
inline void yes(bool i = true) {
    print(i ? "yes" : "no");
}
inline void Yes(bool i = true) {
    print(i ? "Yes" : "No");
}
inline void No() {
    print("No");
}
inline void YES(bool i = true) {
    print(i ? "YES" : "NO");
}
inline void NO() {
    print("NO");
}
inline void Yay(bool i = true) {
    print(i ? "Yay!" : ":(");
}
inline void Possible(bool i = true) {
    print(i ? "Possible" : "Impossible");
}
inline void POSSIBLE(bool i = true) {
    print(i ? "POSSIBLE" : "IMPOSSIBLE");
}

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"

#line 2 "library/Math/fastdiv.hpp"

struct FastDiv{
    using u64=uint64_t;
    using u128=__uint128_t;
    constexpr FastDiv():m(),s(),x(){}
    constexpr FastDiv(int _m)
        :m(_m),s(__lg(m-1)),x(((u128(1)<<(s+64))+m-1)/m){}
    constexpr int get(){return m;}
    constexpr friend u64 operator/(u64 n,const FastDiv& d){
        return (u128(n)*d.x>>d.s)>>64;
    }
    constexpr friend int operator%(u64 n,const FastDiv& d){
        return n-n/d*d.m;
    }
    constexpr pair<u64,int> divmod(u64 n)const{
        u64 q=n/(*this);
        return {q,n-q*m};
    }
    int m,s; u64 x;
};

/**
 * @brief Fast Division
*/
#line 3 "library/Math/dynamic.hpp"

struct Fp {
    using u64 = uint64_t;
    uint v;
    static int get_mod() {
        return _getmod();
    }
    static void set_mod(int _m) {
        bar = FastDiv(_m);
    }
    Fp inv() const {
        int tmp, a = v, b = get_mod(), x = 1, y = 0;
        while (b) {
            tmp = a / b, a -= tmp * b;
            swap(a, b);
            x -= tmp * y;
            swap(x, y);
        }
        if (x < 0) {
            x += get_mod();
        }
        return x;
    }
    Fp() : v(0) {}
    Fp(ll x) {
        v = x % get_mod();
        if (v < 0)
            v += get_mod();
    }
    Fp operator-() const {
        return Fp() - *this;
    }
    Fp pow(ll t) {
        assert(t >= 0);
        Fp res = 1, b = *this;
        while (t) {
            if (t & 1)
                res *= b;
            b *= b;
            t >>= 1;
        }
        return res;
    }
    Fp &operator+=(const Fp &x) {
        v += x.v;
        if (v >= get_mod())
            v -= get_mod();
        return *this;
    }
    Fp &operator-=(const Fp &x) {
        v += get_mod() - x.v;
        if (v >= get_mod())
            v -= get_mod();
        return *this;
    }
    Fp &operator*=(const Fp &x) {
        v = (u64(v) * x.v) % bar;
        return *this;
    }
    Fp &operator/=(const Fp &x) {
        (*this) *= x.inv();
        return *this;
    }
    Fp operator+(const Fp &x) const {
        return Fp(*this) += x;
    }
    Fp operator-(const Fp &x) const {
        return Fp(*this) -= x;
    }
    Fp operator*(const Fp &x) const {
        return Fp(*this) *= x;
    }
    Fp operator/(const Fp &x) const {
        return Fp(*this) /= x;
    }
    bool operator==(const Fp &x) const {
        return v == x.v;
    }
    bool operator!=(const Fp &x) const {
        return v != x.v;
    }
    friend istream &operator>>(istream &is, Fp &x) {
        return is >> x.v;
    }
    friend ostream &operator<<(ostream &os, const Fp &x) {
        return os << x.v;
    }

  private:
    static FastDiv bar;
    static int _getmod() {
        return bar.get();
    }
};
FastDiv Fp::bar(998244353);

void rd(Fp &x) {
    fastio::rd(x.v);
}
void wt(Fp x) {
    fastio::wt(x.v);
}

/**
 * @brief Dynamic Modint
 */
#line 2 "library/Math/comb.hpp"

template <typename T> T Inv(ll n) {
    static int md;
    static vector<T> buf({0, 1});
    if (md != T::get_mod()) {
        md = T::get_mod();
        buf = vector<T>({0, 1});
    }
    assert(n > 0);
    n %= md;
    while (SZ(buf) <= n) {
        int k = SZ(buf), q = (md + k - 1) / k;
        buf.push_back(buf[k * q - md] * q);
    }
    return buf[n];
}

template <typename T> T Fact(ll n, bool inv = 0) {
    static int md;
    static vector<T> buf({1, 1}), ibuf({1, 1});
    if (md != T::get_mod()) {
        md = T::get_mod();
        buf = ibuf = vector<T>({1, 1});
    }
    assert(n >= 0 and n < md);
    while (SZ(buf) <= n) {
        buf.push_back(buf.back() * SZ(buf));
        ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
    }
    return inv ? ibuf[n] : buf[n];
}

template <typename T> T nPr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nCr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
// sum = n, r tuples
template <typename T> T nHr(int n, int r, bool inv = 0) {
    return nCr<T>(n + r - 1, r - 1, inv);
}
// sum = n, a nonzero tuples and b tuples
template <typename T> T choose(int n, int a, int b) {
    if (n == 0)
        return !a;
    return nCr<T>(n + b - 1, a + b - 1);
}

/**
 * @brief Combination
 */
#line 2 "library/DataStructure/unionfind.hpp"

struct UnionFind{
    vector<int> par; int n;
    UnionFind(){}
    UnionFind(int _n):par(_n,-1),n(_n){}
    int root(int x){return par[x]<0?x:par[x]=root(par[x]);}
    bool same(int x,int y){return root(x)==root(y);}
    int size(int x){return -par[root(x)];}
    bool unite(int x,int y){
        x=root(x),y=root(y); if(x==y)return false;
        if(size(x)>size(y))swap(x,y);
        par[y]+=par[x]; par[x]=y; n--; return true;
    }
};

/**
 * @brief Union Find
 */
#line 7 "sol.cpp"

using P = pair<int, int>;
map<P, vector<int>> mp = {
    {{1, 1}, {0, 1}},
    {{1, 2}, {0, 2, 1}},
    {{1, 3}, {0, 5, 2, 1}},
    {{1, 4}, {0, 12, 5, 2, 1}},
    {{1, 5}, {0, 28, 12, 5, 2, 1}},
    {{1, 6}, {0, 64, 28, 12, 5, 2, 1}},
    {{1, 7}, {0, 144, 64, 28, 12, 5, 2, 1}},
    {{1, 8}, {0, 320, 144, 64, 28, 12, 5, 2, 1}},
    {{1, 9}, {0, 704, 320, 144, 64, 28, 12, 5, 2, 1}},
    {{1, 10}, {0, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},
    {{1, 11}, {0, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},
    {{1, 12}, {0, 7168, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},
    {{1, 13}, {0, 15360, 7168, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},
    {{1, 14},
     {0, 32768, 15360, 7168, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},
    {{1, 15},
     {0, 69632, 32768, 15360, 7168, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2,
      1}},
    {{1, 16},
     {0, 147456, 69632, 32768, 15360, 7168, 3328, 1536, 704, 320, 144, 64, 28,
      12, 5, 2, 1}},
    {{1, 17},
     {0, 311296, 147456, 69632, 32768, 15360, 7168, 3328, 1536, 704, 320, 144,
      64, 28, 12, 5, 2, 1}},
    {{1, 18},
     {0, 655360, 311296, 147456, 69632, 32768, 15360, 7168, 3328, 1536, 704,
      320, 144, 64, 28, 12, 5, 2, 1}},
    {{1, 19},
     {0,    1376256, 655360, 311296, 147456, 69632, 32768, 15360, 7168, 3328,
      1536, 704,     320,    144,    64,     28,    12,    5,     2,    1}},
    {{1, 20}, {0,     2883584, 1376256, 655360, 311296, 147456, 69632,
               32768, 15360,   7168,    3328,   1536,   704,    320,
               144,   64,      28,      12,     5,      2,      1}},
    {{1, 21}, {0,     6029312, 2883584, 1376256, 655360, 311296, 147456, 69632,
               32768, 15360,   7168,    3328,    1536,   704,    320,    144,
               64,    28,      12,      5,       2,      1}},
    {{1, 22},
     {0,     12582912, 6029312, 2883584, 1376256, 655360, 311296, 147456,
      69632, 32768,    15360,   7168,    3328,    1536,   704,    320,
      144,   64,       28,      12,      5,       2,      1}},
    {{1, 23},
     {0,      26214400, 12582912, 6029312, 2883584, 1376256, 655360, 311296,
      147456, 69632,    32768,    15360,   7168,    3328,    1536,   704,
      320,    144,      64,       28,      12,      5,       2,      1}},
    {{1, 24}, {0,      54525952, 26214400, 12582912, 6029312, 2883584, 1376256,
               655360, 311296,   147456,   69632,    32768,   15360,   7168,
               3328,   1536,     704,      320,      144,     64,      28,
               12,     5,        2,        1}},
    {{1, 25},
     {0,       113246208, 54525952, 26214400, 12582912, 6029312, 2883584,
      1376256, 655360,    311296,   147456,   69632,    32768,   15360,
      7168,    3328,      1536,     704,      320,      144,     64,
      28,      12,        5,        2,        1}},
    {{2, 2}, {0, 8, 4, 4, 1}},
    {{2, 3}, {0, 40, 17, 14, 10, 6, 1}},
    {{2, 4}, {0, 192, 80, 64, 39, 28, 20, 8, 1}},
    {{2, 5}, {0, 896, 368, 296, 184, 120, 81, 58, 34, 10, 1}},
    {{2, 6}, {0, 4096, 1664, 1344, 856, 560, 368, 240, 167, 112, 52, 12, 1}},
    {{2, 7},
     {0, 18432, 7424, 6016, 3904, 2568, 1712, 1112, 728, 488, 337, 198, 74, 14,
      1}},
    {{2, 8},
     {0, 81920, 32768, 26624, 17536, 11584, 7816, 5136, 3384, 2208, 1456, 992,
      647, 324, 100, 16, 1}},
    {{2, 9},
     {0, 360448, 143360, 116736, 77824, 51584, 35136, 23304, 15520, 10232, 6704,
      4392, 2936, 1976, 1169, 498, 130, 18, 1}},
    {{2, 10}, {0,      1572864, 622592, 507904, 342016, 227328, 156032,
               104256, 70024,   46640,  30888,  20320,  13304,  8784,
               5904,   3792,    1991,   728,    164,    20,     1}},
    {{2, 11},
     {0,      6815744, 2686976, 2195456, 1490944, 993280, 686080, 461184,
      311872, 209416,  139968,  93048,   61440,   40328,  26480,  17624,
      11672,  6952,    3217,    1022,    202,     22,     1}},
    {{2, 12}, {0,       29360128, 11534336, 9437184, 6455296, 4308992, 2992128,
               2021376, 1374592,  929088,   625544,  419408,  279656,  185376,
               122088,  80112,    52888,    35200,   22416,   12160,   4967,
               1388,    244,      24,       1}},
    {{3, 3}, {0, 400, 144, 106, 84, 69, 52, 32, 9, 1}},
    {{3, 4}, {0, 3840, 1360, 952, 705, 550, 445, 360, 270, 164, 62, 12, 1}},
    {{3, 5},
     {0, 35840, 12544, 8720, 6408, 4897, 3772, 2972, 2371, 1873, 1385, 854, 376,
      101, 15, 1}},
    {{3, 6},
     {0, 327680, 113664, 78592, 57936, 44456, 34161, 26334, 20329, 15846, 12510,
      9758, 7131, 4478, 2164, 714, 149, 18, 1}},
    {{3, 7}, {0,      2949120, 1015808, 699392, 516864, 398928, 308296, 238385,
              183352, 140476,  108244,  84130,  65926,  50898,  36946,  23558,
              12123,  4602,    1205,    206,    21,     1}},
    {{3, 8}, {0,       26214400, 8978432, 6160384, 4561920, 3537664, 2748496,
              2136040, 1652625,  1269794, 973997,  746362,  574842,  446028,
              347449,  266040,   192322,  124150,  66909,   28072,   8654,
              1876,    272,      24,      1}},
    {{4, 4},
     {0, 73728, 25600, 17152, 11728, 9040, 7504, 6288, 5340, 4436, 3432, 2360,
      1296, 492, 116, 16, 1}},
    {{4, 5}, {0,      1376256, 471040, 314368, 213248, 158976, 128272,
              105936, 89480,   75998,  64363,  53486,  42473,  31078,
              19942,  10358,   3972,   1054,   186,    20,     1}},
    {{4, 6}, {0,       25165824, 8519680, 5668864, 3856384, 2863104, 2288896,
              1868032, 1553240,  1299184, 1090650, 919360,  774295,  643000,
              517972,  394544,   274893,  167464,  83894,   32492,   9316,
              1920,    272,      24,      1}},
    {{5, 5}, {0,       51380224, 17301504, 11501568, 7749632, 5599232, 4361216,
              3564416, 3023760,  2603088,  2265120,  1971974, 1703398, 1448460,
              1194986, 939036,   687581,   454452,   258314,  119182,  42437,
              11295,   2192,     296,      25,       1}}};

int main() {
    int H, W;
    ll K, mod;
    read(H, W, K, mod);
    if(H>W)swap(H,W);
    Fp::set_mod(mod);

    vector<Fp> pw(H * W + 2);
    rep(x, 1, H * W + 1) pw[x] = Fp(x).pow(K);

    Fp ret;
    auto cnt=mp[{H,W}];
    rep(x,1,H*W+1)ret+=pw[x]*cnt[x];

    Fp sub;
    rep(x, 1, H * W + 1) sub += Inv<Fp>(x);
    ret *= sub;
    ret /= Fp(2).pow(H * W);
    print(ret);
    return 0;
}
0