#1030479 (C++17) No.2983 Christmas Color Grid (Advent Calender ver.)

提出ソース

結果

問題	No.2983 Christmas Color Grid (Advent Calender ver.)
ユーザー	ecottea
提出日時	2024-12-08 15:44:23
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	33,421 bytes
コンパイル時間	5,614 ms
コンパイル使用メモリ	299,048 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-12-08 15:44:31
合計ジャッジ時間	7,524 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	AC	2 ms 5,248 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	2 ms 5,248 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	AC	2 ms 5,248 KB
testcase_41	AC	2 ms 5,248 KB
testcase_42	AC	2 ms 5,248 KB
testcase_43	AC	2 ms 5,248 KB
testcase_44	AC	2 ms 5,248 KB
testcase_45	AC	1 ms 5,248 KB
testcase_46	AC	2 ms 5,248 KB
testcase_47	AC	2 ms 5,248 KB
testcase_48	AC	2 ms 5,248 KB
testcase_49	AC	2 ms 5,248 KB
testcase_50	AC	2 ms 5,248 KB
testcase_51	AC	2 ms 5,248 KB
testcase_52	AC	1 ms 5,248 KB
testcase_53	AC	2 ms 5,248 KB
testcase_54	AC	2 ms 5,248 KB
testcase_55	AC	1 ms 5,248 KB
testcase_56	AC	2 ms 5,248 KB
testcase_57	AC	1 ms 5,248 KB
testcase_58	AC	2 ms 5,248 KB
testcase_59	AC	2 ms 5,248 KB
testcase_60	AC	2 ms 5,248 KB
testcase_61	AC	2 ms 5,248 KB
testcase_62	AC	2 ms 5,248 KB
testcase_63	AC	2 ms 5,248 KB
testcase_64	AC	2 ms 5,248 KB
testcase_65	AC	2 ms 5,248 KB
testcase_66	AC	1 ms 5,248 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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 | }
      | ^

ソースコード

raw source code

#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/SUMOVERALL

	repi(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/4
	dump(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_b

		Assert(abs(i) <= n);

		return i >= 0 ? powB[i] : powB_inv[-i];
	}

#ifdef _MSC_VER
	friend 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_h

		Assert(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_g

		Assert(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_h

		auto 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_h

		T 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/617

		T 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=statement

		if (num >= 0) return num / dnm;
		else return -((-num + dnm - 1) / dnm);
	}

	// 自身の ceil を返す．
	T ceil() const {
		// verify : https://www.codechef.com/problems/LINEFIT?tab=statement

		if (num >= 0) return (num + dnm - 1) / dnm;
		else return -((-num) / dnm);
	}

	// 自身が整数かを返す．
	bool integerQ() const {
		// verify : https://atcoder.jp/contests/ttpc2022/tasks/ttpc2022_g

		return num % dnm == 0;
	}

#ifdef _MSC_VER
	friend 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));
}