結果
| 問題 | No.2983 Christmas Color Grid (Advent Calender ver.) |
| ユーザー |
 ecottea
|
| 提出日時 | 2024-12-08 15:44:23 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 33,421 bytes |
| コンパイル時間 | 5,927 ms |
| コンパイル使用メモリ | 285,568 KB |
| 最終ジャッジ日時 | 2025-02-26 11:35:33 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 31 WA * 33 |
コンパイルメッセージ
main.cpp: In function ‘mint WA(int, int, ll, int)’:
main.cpp:690:1: warning: control reaches end of non-void function [-Wreturn-type]
690 | }
| ^
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用// 警告の抑制#define _CRT_SECURE_NO_WARNINGS// ライブラリの読み込み#include <bits/stdc++.h>using namespace std;// 型名の短縮using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;using Graph = vvi;// 定数の定義const double PI = acos(-1);int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）int DY[4] = { 0, 1, 0, -1 };int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;// 入出力高速化struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;// 汎用マクロの定義#define all(a) (a).begin(), (a).end()#define sz(x) ((int)(x).size())#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定// 汎用関数の定義template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら trueを返す）template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら trueを返す）template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod// 演算子オーバーロードtemplate <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }#endif // 折りたたみ用#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#ifdef _MSC_VER#include "localACL.hpp"#endif//using mint = modint998244353;//using mint = static_modint<1000000007>;using mint = modint; // mint::set_mod(m);namespace atcoder {inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }}using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;#endif#ifdef _MSC_VER // 手元環境（Visual Studio）#include "local.hpp"#else // 提出用（gcc）inline int popcount(int n) { return __builtin_popcount(n); }inline int popcount(ll n) { return __builtin_popcountll(n); }inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }#define dump(...)#define dumpel(...)#define dump_list(v)#define dump_mat(v)#define input_from_file(f)#define output_to_file(f)#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す#endif//【mint → 有理数】（実験用）/** x を分母と分子の絶対値が v_max 以下の有理数表示に変換する（不可能ならそのまま）*/string mint_to_frac(mint x, int v_max = 31595) {// verify : https://www.codechef.com/problems/SUMOVERALLrepi(dnm, 1, v_max) {int num = (x * dnm).val();if (num == 0) {return "0";}if (num <= v_max) {if (dnm == 1) return to_string(num);return to_string(num) + "/" + to_string(dnm);}if (mint::mod() - num <= v_max) {if (dnm == 1) return "-" + to_string(mint::mod() - num);return "-" + to_string(mint::mod() - num) + "/" + to_string(dnm);}}return to_string(x.val());}// さすがに間に合わない．ていうか思いっきり誤読してた．void WA() {int h, w; ll k; int m;cin >> h >> w >> k >> m;mint::set_mod(m);dump(mint_to_frac(499122177));dump(mint_to_frac(249561091)); // 11/4dump(0 + 1 + 1 + 1 + (1 + 1) + 4 + 4 + 9);int n = h * w;vm pow_i(n + 1);repi(i, 0, n) pow_i[i] = mint(i).pow(k);mint res = 0;repb(set, n) {dsu d(n); mint val = 0;rep(i, h) rep(j, w - 1) {if (!getb(set, i * w + j)) continue;if (!getb(set, i * w + (j + 1))) continue;d.merge(i * w + j, i * w + (j + 1));}rep(i, h - 1) rep(j, w) {if (!getb(set, i * w + j)) continue;if (!getb(set, (i + 1) * w + j)) continue;d.merge(i * w + j, (i + 1) * w + j);}auto gs = d.groups();repe(g, gs) {if (sz(g) == 1 && !getb(set, g[0])) continue;val += pow_i[sz(g)];}// dump(set, val);res += val;}res /= mint(2).pow(n);EXIT(res);}//【累乗（mint 利用）】/** Pow_mint(mint B, int n) : O(n)* 底を B とし，B^0 から B^n まで計算可能として初期化する．** build_neg() : O(n)* B^(-1) から B^(-n) も計算可能にする．* 制約 : B は mint の法と互いに素** mint [](int i) : O(1)* B^i を返す．*/class Pow_mint {int n;vm powB, powB_inv;public:Pow_mint(mint B, int n) : n(max(n, 2)) {// verify : https://yukicoder.me/problems/no/2709// B の累乗を計算する．powB.resize(n + 1);powB[0] = 1;rep(i, n) powB[i + 1] = powB[i] * B;};Pow_mint() : n(0) {}// 負冪も計算できるようにする．void build_neg() {// verify : https://atcoder.jp/contests/arc116/tasks/arc116_b// B の逆元の累乗を計算する．mint invB = powB[1].inv();powB_inv.resize(n + 1);powB_inv[0] = 1;rep(i, n) powB_inv[i + 1] = powB_inv[i] * invB;}// B^i を返す．mint const& operator[](int i) const {// verify : https://atcoder.jp/contests/arc116/tasks/arc116_bAssert(abs(i) <= n);return i >= 0 ? powB[i] : powB_inv[-i];}#ifdef _MSC_VERfriend ostream& operator<<(ostream& os, const Pow_mint& pw) {os << pw.powB << endl;os << pw.powB_inv << endl;return os;}#endif};// AC51, TLE16．後は高速化だけだmint TLE(int h, int w, ll k, int m) {mint::set_mod(m);int n = h * w;vm pow_i(n + 1);repi(i, 0, n) pow_i[i] = mint(i).pow(k);vvm bin(n + 1, vm(n + 1));bin[0][0] = 1;repi(i, 1, n) repi(j, 0, i) {if (j > 0) bin[i][j] += bin[i - 1][j - 1];if (j < i) bin[i][j] += bin[i - 1][j];}vvm bin_inv(n + 1, vm(n + 1));repi(i, 0, n) repi(j, 0, i) {bin_inv[i][j] = bin[i][j].inv();}Pow_mint pow2(2, n);pow2.build_neg();vm inv(n + 1);repi(i, 1, n) inv[i] = mint(i).inv();mint res = 0;// ひとまず bit 全探索．もしや連結 DP 的なことしないとだめ？repb(set, n) {if (set == 0) continue;vvi a(h, vi(w));rep(i, h) rep(j, w) a[i][j] = getb(set, i * w + j);dsu d(n); int x0 = 0, y0 = 0;rep(i, h) rep(j, w - 1) {if (!a[i][j]) continue;x0 = i, y0 = j;if (!a[i][j + 1]) continue;d.merge(i * w + j, i * w + (j + 1));}rep(i, h - 1) rep(j, w) {if (!a[i][j]) continue;x0 = i, y0 = j;if (!a[i + 1][j]) continue;d.merge(i * w + j, (i + 1) * w + j);}int pc = popcount(set);if (d.size(x0 * w + y0) != pc) continue;rep(i, h) {rep(j, w - 1) {if (a[i][j] != 0) continue;if (a[i][j + 1] == 1) a[i][j] = -1;}repi(j, 1, w - 1) {if (a[i][j] != 0) continue;if (a[i][j - 1] == 1) a[i][j] = -1;}}rep(j, w) {rep(i, h - 1) {if (a[i][j] != 0) continue;if (a[i + 1][j] == 1) a[i][j] = -1;}repi(i, 1, h - 1) {if (a[i][j] != 0) continue;if (a[i - 1][j] == 1) a[i][j] = -1;}}int cnt = 0;rep(i, h) rep(j, w) cnt += a[i][j] != 0;repi(k, 1, n) {mint p0 = bin_inv[n][k] * pow2[-k];mint w1 = pow2[k - cnt] * bin[n][k] * inv[n - k + 1];res += p0 * w1 * pow_i[pc];}}return res;}//【有理数】/** Frac<T>() : O(1)* 0 で初期化する．* 制約：T は int, ll, __int128, boost::multiprecision::int256_t 等** Frac<T>(T num) : O(1)* num で初期化する．** Frac<T>(T num, T dnm) : O(1)* num / dnm で初期化する（分母は自動的に正にする）** a == b, a != b, a < b, a > b, a <= b, a >= b : O(1)* 大小比較を行う（分母が共通の場合は積はとらない）** a + b, a - b, a * b, a / b : O(1)* 加減乗除を行う（和と差については，分母が共通の場合は積はとらない）* 一方が整数でも構わない．複合代入演算子も使用可．** reduction() : O(log min(num, dnm))* 自身の約分を行う．** together(Frac& a, Frac& b) : O(log min(a.dnm, b.dnm))* a と b を通分する．** together(vector<Frac>& as) : O(|as| log dnm)* as を通分する．** T floor() : O(1)* 自身の floor を返す．** T ceil() : O(1)* 自身の ceil を返す．** bool integerQ() : O(1)* 自身が整数かを返す．*/template <class T = ll>struct Frac {// 分子，分母T num, dnm;// コンストラクタFrac() : num(0), dnm(1) {}Frac(T num) : num(num), dnm(1) {}Frac(T num_, T dnm_) : num(num_), dnm(dnm_) {// verify : https://atcoder.jp/contests/abc244/tasks/abc244_hAssert(dnm != 0);if (dnm < 0) { num *= -1; dnm *= -1; }}// 代入Frac(const Frac& b) = default;Frac& operator=(const Frac& b) = default;// キャストoperator double() const { return (double)num / (double)dnm; }// 比較bool operator==(const Frac& b) const {// 分母が等しいときはオーバーフロー防止のために掛け算はせず比較する．if (dnm == b.dnm) return num == b.num;return num * b.dnm == b.num * dnm;}bool operator!=(const Frac& b) const { return !(*this == b); }bool operator<(const Frac& b) const {// verify : https://atcoder.jp/contests/abc308/tasks/abc308_c// 分母が等しいときはオーバーフロー防止のために掛け算はせず比較する．if (dnm == b.dnm) return num < b.num;return (num * b.dnm < b.num * dnm);}bool operator>=(const Frac& b) const { return !(*this < b); }bool operator>(const Frac& b) const { return b < *this; }bool operator<=(const Frac& b) const { return !(*this > b); }// 整数との比較bool operator==(T b) const { return num == b * dnm; }bool operator!=(T b) const { return num != b * dnm; }bool operator<(T b) const { return num < b * dnm; }bool operator>=(T b) const { return num >= b * dnm; }bool operator>(T b) const { return num > b * dnm; }bool operator<=(T b) const { return num <= b * dnm; }friend bool operator==(T a, const Frac& b) { return a * b.dnm == b.num; }friend bool operator!=(T a, const Frac& b) { return a * b.dnm != b.num; }friend bool operator<(T a, const Frac& b) { return a * b.dnm < b.num; }friend bool operator>=(T a, const Frac& b) { return a * b.dnm >= b.num; }friend bool operator>(T a, const Frac& b) { return a * b.dnm > b.num; }friend bool operator<=(T a, const Frac& b) { return a * b.dnm <= b.num; }// 四則演算Frac& operator+=(const Frac& b) {// verify : https://www.codechef.com/problems/ARCTR// 分母が等しいときはオーバーフロー防止のために掛け算はせず加算する．if (dnm == b.dnm) num += b.num;else { num = num * b.dnm + b.num * dnm; dnm *= b.dnm; }return *this;}Frac& operator-=(const Frac& b) {// verify : https://www.codechef.com/problems/ARCTR// 分母が等しいときはオーバーフロー防止のために掛け算はせず加算する．if (dnm == b.dnm) num -= b.num;else { num = num * b.dnm - b.num * dnm; dnm *= b.dnm; }return *this;}Frac& operator*=(const Frac& b) { num *= b.num; dnm *= b.dnm; return *this; }Frac& operator/=(const Frac& b) {// verify : https://atcoder.jp/contests/abc301/tasks/abc301_gAssert(b.num != 0);num *= b.dnm; dnm *= b.num;if (dnm < 0) { num *= -1; dnm *= -1; }return *this;}Frac operator+(const Frac& b) const { Frac a = *this; return a += b; }Frac operator-(const Frac& b) const { Frac a = *this; return a -= b; }Frac operator*(const Frac& b) const { Frac a = *this; return a *= b; }Frac operator/(const Frac& b) const { Frac a = *this; return a /= b; }Frac operator-() const { return Frac(*this) *= Frac(-1); }// 整数との四則演算Frac& operator+=(T c) { num += dnm * c; return *this; }Frac& operator-=(T c) { num -= dnm * c; return *this; }Frac& operator*=(T c) { num *= c; return *this; }Frac& operator/=(T c) {Assert(c != T(0));dnm *= c;if (dnm < 0) { num *= -1; dnm *= -1; }return *this;}Frac operator+(T c) const { Frac a = *this; return a += c; }Frac operator-(T c) const { Frac a = *this; return a -= c; }Frac operator*(T c) const { Frac a = *this; return a *= c; }Frac operator/(T c) const { Frac a = *this; return a /= c; }friend Frac operator+(T c, const Frac& a) { return a + c; }friend Frac operator-(T c, const Frac& a) { return Frac(c) - a; }friend Frac operator*(T c, const Frac& a) { return a * c; }friend Frac operator/(T c, const Frac& a) { return Frac(c) / a; }// 約分を行う．void reduction() {// verify : https://atcoder.jp/contests/abc229/tasks/abc229_hauto g = gcd(num, dnm);num /= g; dnm /= g;}// a と b を通分する．friend void together(Frac& a, Frac& b) {// verify : https://atcoder.jp/contests/abc229/tasks/abc229_hT dnm = lcm(a.dnm, b.dnm);a.num *= dnm / a.dnm; a.dnm = dnm;b.num *= dnm / b.dnm; b.dnm = dnm;}// as を通分する．friend void together(vector<Frac>& as) {// verify : https://yukicoder.me/problems/617T dnm = 1;repe(a, as) dnm = lcm(dnm, a.dnm);repea(a, as) {a.num *= dnm / a.dnm;a.dnm = dnm;}}// 自身の floor を返す．T floor() const {// verify : https://www.codechef.com/problems/LINEFIT?tab=statementif (num >= 0) return num / dnm;else return -((-num + dnm - 1) / dnm);}// 自身の ceil を返す．T ceil() const {// verify : https://www.codechef.com/problems/LINEFIT?tab=statementif (num >= 0) return (num + dnm - 1) / dnm;else return -((-num) / dnm);}// 自身が整数かを返す．bool integerQ() const {// verify : https://atcoder.jp/contests/ttpc2022/tasks/ttpc2022_greturn num % dnm == 0;}#ifdef _MSC_VERfriend ostream& operator<<(ostream& os, const Frac& a) { os << a.num << '/' << a.dnm; return os; }#endif};using F = Frac<ll>;vector<F> umekomi_sub(int h, int w) {int n = h * w;vvl bin(n + 1, vl(n + 1));bin[0][0] = 1;repi(i, 1, n) repi(j, 0, i) {if (j > 0) bin[i][j] += bin[i - 1][j - 1];if (j < i) bin[i][j] += bin[i - 1][j];}vector<F> coef(n + 1);repb(set, n) {if (set == 0) continue;vvi a(h, vi(w));rep(i, h) rep(j, w) a[i][j] = getb(set, i * w + j);dsu d(n); int x0 = 0, y0 = 0;rep(i, h) rep(j, w - 1) {if (!a[i][j]) continue;x0 = i, y0 = j;if (!a[i][j + 1]) continue;d.merge(i * w + j, i * w + (j + 1));}rep(i, h - 1) rep(j, w) {if (!a[i][j]) continue;x0 = i, y0 = j;if (!a[i + 1][j]) continue;d.merge(i * w + j, (i + 1) * w + j);}int pc = popcount(set);if (d.size(x0 * w + y0) != pc) continue;rep(i, h) {rep(j, w - 1) {if (a[i][j] != 0) continue;if (a[i][j + 1] == 1) a[i][j] = -1;}repi(j, 1, w - 1) {if (a[i][j] != 0) continue;if (a[i][j - 1] == 1) a[i][j] = -1;}}rep(j, w) {rep(i, h - 1) {if (a[i][j] != 0) continue;if (a[i + 1][j] == 1) a[i][j] = -1;}repi(i, 1, h - 1) {if (a[i][j] != 0) continue;if (a[i - 1][j] == 1) a[i][j] = -1;}}int cnt = 0;rep(i, h) rep(j, w) cnt += a[i][j] != 0;repi(t, 1, n) {coef[pc] += F(1, (ll)(n - t + 1) << cnt);coef[pc].reduction();}}return coef;}int N = 25;void umekomi() {cout << "vvl coef = {" << endl;repi(h, 1, N) repi(w, 1, min(N / h, h)) {dump(h, w);auto c = umekomi_sub(h, w);int n = sz(c);cout << "{";rep(i, n) {cout << c[i].num << "," << c[i].dnm << ",}"[i == n - 1];}cout << "," << endl;}cout << "};" << endl;}// 負の数が見えるのでどうみてもオーバーフローしているvvl coef = {{0,1,1,2},{0,1,3,4,3,8},{0,1,25,24,25,48,25,48,25,192},{0,1,55,48,11,24,11,48},{0,1,49,32,833,1280,343,640,49,128,147,640,49,1280},{0,1,35645,16128,7129,8960,377837,645120,7129,15360,163967,430080,92677,322560,7129,40320,7129,143360,7129,1290240},{0,1,25,16,125,192,25,96,25,192},{0,1,2283,1120,761,896,761,1120,29679,71680,761,2560,761,3584,761,8960,761,71680},{0,1,86021,29568,1462357,1419264,1462357,2027520,4042987,7569408,430105,1032192,7655869,22708224,86021,315392,258063,1261568,3526861,28385280,2666651,56770560,86021,9461760,86021,113541120},{0,1,2436559,640640,12182795,9225216,163249453,184504320,1785997747,2952069120,275331167,590413824,163249453,421724160,319189229,984023040,216853751,787218432,2702143931,11808276480,2436559,13762560,143756981,1180827648,21929031,328007680,99898919,3936092160,70660211,11808276480,2436559,2952069120,2436559,47233105920},{0,1,959,480,137,160,137,384,137,960,137,1920},{0,1,7381,2880,169763,161280,273097,322560,169763,322560,7381,21504,66429,286720,214049,1290240,125477,1290240,7381,258048,7381,2580480},{0,1,1195757,329472,8370299,6589440,130337513,147603456,106422373,164003840,5855622029,11808276480,1127598851,2952069120,888447451,2952069120,2835139847,11808276480,2239652861,11808276480,331224689,2361655296,72941177,843448320,56200579,1476034560,120771457,11808276480,1195757,787218432,1195757,11808276480},{0,1,55835135,11824384,6421040525,3972993024,17141386445,15891972096,390845945,534183936,11557872945,21189296128,4209300435254953,229208100962304,364695846540223,-431294335942656,-469844320494061,-43988960673792,5624258774821,-3027910000640,153800933357389,259705012224000,52704317408017,31301126062080,34816218174619,35774074454016,18460581291305,-10562423488512,9571047894085,-11099193737216,1428000710713,1053516890112,-215539936141,108837994496,-2508642759859,-583469629440,3231665957243,-1497391693824,-1413151237291,132066050048,9267547869,-3625170501632},{0,1,238367657269,40794124800,34052522467,17306598400,306472702203,234304716800,400304745176869,351073302773760,-1809131065877453,-2137066818109440,250725234246467,-1306334298898432,-2593670794031,-14007352164352,30567741816427,375901409771520,8562141569419,-99485032120320,-108004075813145,84845518651392,-44763767871997,40485703909376,11878706812197,-24755386187776,118883917941,2431354142720,-3047036092987,-3473286365184,1812078952711,-3778900131840,-894204730199,1692753985536,-200488732313,706387902464,481362960833,111937585152,64547530401,-46439333888,-39155088007,-20937965568,-93975098869,73551314944,-6929300537,-14394851328,8515230331,21139292160,22326783151,1610612736,-36512161789,59592671232},{0,1,49,20,343,320,147,320,49,256,49,640,49,1280},{0,1,86021,27720,1118273,887040,86021,84480,9204247,14192640,86021,202752,1978483,7096320,86021,473088,14365507,113541120,86021,1013760,1118273,28385280,86021,9461760,86021,113541120},{0,1,14274301,3267264,528149137,348508160,4382210407,4182097920,1013475371,1312030720,79322290657,133827133440,162541465487,356872355840,-4361144274146819,-2123902211850240,-471366059511639,-486267192082432,-27793726206509,-116780422922240,25706151590961,-10440266481664,12364720846799,14890859233280,-150838740533,22302771118080,20932729094075,19508376895488,-120650886869,264162508800,10526489812021,10666725343232,17441826335401,11801961955328,-327786059227,-3844079616,14274301,1070617067520},{0,1,1347822955,237965728,6739114775,3514570752,233173371215,182757679104,-11833668976342031,10436235914772480,3143676128632205,-2118728464269312,2009776789529089,4171401331212288,-91104419443903,-90156341133312,888231274586203,-770347313922048,187289845312517,-84319754256384,-1280338248549,-189448457289728,-38853112337561,2624690585600,10455975265223,980594720768,-5436229973579,-10178569175040,-11004491517463,5966313553920,5196781338181,-8232596668416,-2536393313221,-1609807429632,-1110981122825,1073976705024,169072560557,-231525580800,542035613607,507410120704,-101776598911,-77510737920,-1957736309,-2422210560,12761702071,60448309248,-8482712707,-3925868544,-245973312601,-269777633280},{0,1,3267,1120,363,280,363,640,1089,4480,363,3584,363,8960,363,17920},{0,1,1171733,320320,33980257,23063040,55071451,46126080,71475713,92252160,125375431,246005760,125375431,369008640,162870887,738017280,1171733,8110080,71475713,738017280,394874021,5904138240,1171733,29818880,43354121,2952069120,1171733,421724160,1171733,5904138240},{0,1,848612385,165541376,584599643,331082752,12880050199,10594648064,38074409007,42378592256,102856694908617,-21840086958080,210319809237817,608518545604608,1049036260948307,2609475999498240,473871662116233,-1835976846475264,-18222306474059,13186396848128,104002986425953,117544153251840,-17113298753941,9366333816832,13530358149421,20368630743040,-51960746463217,-58999814750208,-4617253306819,-10293778317312,-1495395994129,-7505002364928,-1181176090397,-333698826240,-1643758510663,-2100993982464,944925426133,701119856640,1282141975949,183962173440,310257833141,585155739648,-972431275817,1021430464512},{0,1,761,224,6849,4480,761,1120,761,2560,2283,17920,761,14336,761,35840,761,71680},{0,1,2436559,576576,2436559,1441440,2436559,1774080,333808583,369008640,441017179,738017280,2380518143,5904138240,260711813,984023040,114518273,656015360,56040857,492011520,2436559,32440320,75533329,1476034560,1576453673,47233105920,21929031,1312030720,12182795,2361655296,2436559,2952069120,2436559,47233105920},{0,1,33695573875,5711177472,184651744835,91378839552,63347678885,45689419776,-10770590266384927,1481485761380352,7349768691017537,-15677279490277376,-3337780132238921,1085120383549440,1174832905561227,1486579012993024,-262260592643227,273664847118336,721808993266193,915883119607808,487242592427707,-487362018672640,-2856977520359,-20385928052736,-16136323637711,15978486300672,-17678344805777,29832373075968,-10633340526425,10491262926848,-16825965718491,10668128337920,-4882337678321,-2070845325312,-865720286515,-1081929105408,267707119667,-456608710656,323546192641,-53653536768,380133310475,210587615232,39923047313,-104085848064,12761702071,60448309248,-8482712707,-3925868544,-245973312601,-269777633280},{0,1,78419,20160,7129,4032,7129,8960,7129,20160,7129,46080,7129,107520,7129,258048,7129,645120,7129,1290240},{0,1,14274301,2970240,14274301,7468032,271211719,174254080,271211719,261381120,442503331,643399680,2612197083,5576130560,13860346271,44609044480,1384607197,6691356672,-548809828034933,-111199589498880,307479472486477,38403940024320,-20573821606363,14890468638720,-75147280670993,255520776126464,-49328298594803,57519704113152,-38408217891641,60314112491520,11050724578669,-4182025175040,1050809718773,-2510813134848,-327786059227,-3844079616,14274301,1070617067520},{0,1,7381,1680,81191,40320,7381,8064,7381,17920,7381,40320,7381,92160,7381,215040,7381,516096,7381,1290240,7381,2580480},{0,1,55835135,10346336,55835135,26138112,1730889185,993248256,9324467545,7945986048,2065899995,2648662016,68063029565,127135776768,5044854303100663,3539385093193728,-1096717755530267,-962768268165120,-1801791672050169,-1227744382812160,-370810336666119,-268672763428864,-216908779786379,435663380414464,-23199250589653,-44941474529280,-20600735037,37221302272,16593248903685,-11103972098048,-2606986320471,-1719158177792,-5640856205003,-1795078225920,374443766671,2690232877056,2495020756583,-846238580736,-1413151237291,132066050048,9267547869,-3625170501632},{0,1,1088243,221760,83711,36960,83711,80640,83711,177408,83711,394240,83711,887040,83711,2027520,83711,4730880,83711,11354112,83711,28385280,83711,56770560},{0,1,19093197,3183488,782821077,331082752,1279244199,662165504,19093197,14553088,9260200545,10594648064,6396220995,10594648064,1478234299769257,1171565394264064,3065938472776297,2208895111004160,1867499800311,-6840532336640,43912839181639,190428736389120,-26078287651551,41322224287744,32763646471579,-29526509764608,-34295600193637,-56395227463680,7257934304657,-22269803888640,26690506697567,27825440555008,-17208997709361,-16783499067392,2621908878583,6407663386624,-806211220489,108515033088,516530704013,659445252096,-1690667353,3120562176,-116835980953,149887647744,750807786857,785911906304},{0,1,86021,15840,1118273,443520,86021,73920,86021,161280,86021,354816,86021,788480,86021,1774080,86021,4055040,86021,9461760,86021,22708224,86021,56770560,86021,113541120},{0,1,1347822955,203970624,1347822955,519197952,4043468865,1903725824,265521122135,182757679104,354477437165,365515358208,-114241980632191,-119723102437376,1892453408363047,702581274968064,-3529978859373791,2904491814813696,-663452612017451,410265833177088,-649152336111773,567403264081920,-785555795993,2441001041920,90155000871359,-49948624158720,36941521206695,15495193427968,69897324848213,-45439244042240,-385717143071,-1070604484608,-7470469720777,1255774617600,-4190032120109,-6821370658816,684456484441,-178425692160,224915591153,150397255680,-738935109917,835639574528,27087160405,-49727668224,-137102652455,187971928064,-8482712707,-3925868544,-245973312601,-269777633280},{0,1,1145993,192192,1145993,411840,1145993,887040,1145993,1921920,1145993,4193280,1145993,9225216,1145993,20500480,1145993,46126080,1145993,105431040,1145993,246005760,1145993,590413824,1145993,1476034560,1145993,2952069120},{0,1,1171733,180180,1171733,384384,1171733,823680,1171733,1774080,1171733,3843840,1171733,8386560,1171733,18450432,1171733,41000960,1171733,92252160,1171733,210862080,1171733,492011520,1171733,1180827648,1171733,2952069120,1171733,5904138240},{0,1,20327869,2882880,1195757,360360,1195757,768768,1195757,1647360,1195757,3548160,1195757,7687680,1195757,16773120,1195757,36900864,1195757,82001920,1195757,184504320,1195757,421724160,1195757,984023040,1195757,2361655296,1195757,5904138240,1195757,11808276480},{0,1,2436559,320320,41421503,11531520,2436559,1441440,2436559,3075072,2436559,6589440,2436559,14192640,2436559,30750720,2436559,67092480,2436559,147603456,2436559,328007680,2436559,738017280,2436559,1686896640,2436559,3936092160,2436559,9446621184,2436559,23616552960,2436559,47233105920},{0,1,800702237,98017920,42142223,10890880,42142223,23063040,42142223,49008960,42142223,104552448,42142223,224040960,42142223,482549760,42142223,1045524480,42142223,2281144320,42142223,5018517504,42142223,11152261120,42142223,25092587520,42142223,57354485760,42142223,133827133440,42142223,321185120256,42142223,802962800640,42142223,1605925601280},{0,1,14274301,1633632,271211719,65345280,42822903,21781760,14274301,15375360,14274301,32672640,14274301,69701632,14274301,149360640,14274301,321699840,14274301,697016320,14274301,1520762880,14274301,3345678336,42822903,22304522240,14274301,16728391680,14274301,38236323840,14274301,89218088960,-1787932878983,344465604608,-1303950192155,-3256224841728,14274301,1070617067520},{0,1,275295799,29560960,275295799,62078016,275295799,130690560,825887397,827706880,275295799,584263680,275295799,1241560320,275295799,2648662016,275295799,5675704320,275295799,12224593920,275295799,26486620160,275295799,57788989440,275295799,127135776768,825887397,847571845120,65410610146425,93957656018944,4786060919759,-4886139764736,23642574506203,-17981528604672,16819929851769,17467355168768,1839536786597,1142591324160,46425598795,8711678459904},{0,1,55835135,5643456,55835135,11824384,279175675,124156032,55835135,52276224,167505405,331082752,55835135,233705472,55835135,496624128,279175675,5297324032,55835135,2270281728,55835135,4889837568,55835135,10594648064,55835135,23115595776,279175675,254271553536,170320986437,2485832908800,8941805009051,48798618615808,-2871321026473,-2213120311296,8501642949633,16276873281536,8636163551881,6891728011264,-4137557808487,103003717632,9267547869,-3625170501632},{0,1,433735219,41385344,18858053,3762304,56574159,23648768,94290265,82770688,18858053,34850816,169722477,662165504,18858053,155803648,18858053,331082752,282870795,10594648064,18858053,1513521152,18858053,3259891712,56574159,21189296128,18858053,15410397184,37742947097393,-8489672376320,-3000481507433,-3316182417408,-34916313489313,-12998533447680,888128006267,949884026880,8547088440341,-7164601040896,-3836699266203,3525060853760,-1480221286303,540612231168,-972431275817,1021430464512},{0,1,57279591,5173168,439143531,82770688,19093197,7524608,57279591,47297536,95465985,165541376,19093197,69701632,171838773,1324331008,19093197,311607296,19093197,662165504,286397955,21189296128,19093197,3027042304,19093197,6519783424,57279591,42378592256,-34538067553667,100268227166208,66484579593421,-46285521420288,4499011787431,-1523199246336,-293810963299,-13510901760,-4219822149817,7576976621568,-139371261077,13673431040,1548191421543,-1769727852544,139110019843,-174315274240,750807786857,785911906304},{0,1,11107917475,951862912,1332950097,237965728,444316699,165541376,444316699,346131968,1332950097,2175686656,2221583495,7614903296,444316699,3206275072,3998850291,60919226368,444316699,14333935616,444316699,30459613184,6664750485,974707621888,-20596024359909,-24346096173056,-7838686507029,-40238080065536,45945812519647,-31055708160000,22704585708551,-29656004689920,9197467061,259323330560,2914896472939,7847081410560,1001086427,7649766670336,-169299566791,-44795166720,295626063477,-136331657216,169688426497,113145544704,155568658739,252664872960,126471045587,-512577503232},{0,1,1347822955,109830336,33695573875,5711177472,1347822955,475931456,1347822955,993248256,1347822955,2076791808,1347822955,4351373312,6739114775,45689419776,1347822955,19237650432,4043468865,121838452736,1347822955,86003613696,1347822955,182757679104,103460041105453,461902198865920,113023460163461,-32844189794304,44273841710575,10446743535616,-3269272237765,37236458913792,-35106133203071,14619796045824,26641422773,101355356160,61193650685,-1949495721984,2203631668809,-2730940694528,1692730825103,-699207254016,-38733843419,-405673082880,19323148461,-9395240960,70964973629,-98650030080,-245973312601,-269777633280},{0,1,306472702203,23796572800,34052522467,5491516800,34052522467,11422354944,34052522467,23796572800,34052522467,49662412800,34052522467,103839590400,34052522467,217568665600,34052522467,456894197760,34052522467,961882521600,102157567401,6091922636800,1106638648682467,-1039652891000832,60598767714493,-54458709688320,-171310915471197,275907223224320,-53963429606223,104537894944768,18086061280249,-12447249334272,3973427672621,-3357142941696,-4148513320231,-4868957798400,4245144075827,-3181337640960,-4011647405717,3882616881152,-2855560967,-3246391296,345659344117,706387902464,28659538765,-221861904384,-61313229421,-213137752064,8498030777,-52344913920,-36512161789,59592671232}};// 埋め込み計算がオーバーフローしているmint WA(int h0, int w0, ll k, int m) {mint::set_mod(m);if (h0 < w0) swap(h0, w0);int pt = 0;repi(h, 1, N) repi(w, 1, min(N / h, h)) {if (h == h0 && w == w0) {auto c = coef[pt];mint res = 0;rep(t, sz(c) / 2) {res += mint(t).pow(k) * c[2 * t + 0] / c[2 * t + 1];}return res;}pt++;}}int main() {// input_from_file("input.txt");// output_to_file("output.txt");// umekomi(); return 0;int h, w; ll k; int m;cin >> h >> w >> k >> m;// dump(TLE(h, w, k, m));EXIT(WA(h, w, k, m));}