#include using namespace std; constexpr int mod = 998244353; /** * @brief Montgomery ModInt */ template< uint32_t mod, bool fast = false > struct MontgomeryModInt { using mint = MontgomeryModInt; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; i++) ret *= 2 - mod * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod) % mod; static_assert(r * mod == 1, "invalid, r * mod != 1"); static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); u32 x; MontgomeryModInt(): x{} {} MontgomeryModInt(const i64 &a) : x(reduce(u64(fast ? a : (a % mod + mod)) * n2)) {} static constexpr u32 reduce(const u64 &b) { return u32(b >> 32) + mod - u32((u64(u32(b) * r) * mod) >> 32); } mint &operator+=(const mint &p) { if (i32(x += p.x - 2 * mod) < 0) x += 2 * mod; return *this; } mint &operator-=(const mint &p) { if (i32(x -= p.x) < 0) x += 2 * mod; return *this; } mint &operator*=(const mint &p) { x = reduce(u64(x) * p.x); return *this; } mint &operator/=(const mint &p) { *this *= p.inverse(); return *this; } mint operator-() const { return mint() - *this; } mint operator+(const mint &p) const { return mint(*this) += p; } mint operator-(const mint &p) const { return mint(*this) -= p; } mint operator*(const mint &p) const { return mint(*this) *= p; } mint operator/(const mint &p) const { return mint(*this) /= p; } bool operator==(const mint &p) const { return (x >= mod ? x - mod : x) == (p.x >= mod ? p.x - mod : p.x); } bool operator!=(const mint &p) const { return (x >= mod ? x - mod : x) != (p.x >= mod ? p.x - mod : p.x); } u32 get() const { u32 ret = reduce(x); return ret >= mod ? ret - mod : ret; } mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } mint inverse() const { return pow(mod - 2); } friend ostream &operator<<(ostream &os, const mint &p) { return os << p.get(); } friend istream &operator>>(istream &is, mint &a) { i64 t; is >> t; a = mint(t); return is; } static u32 get_mod() { return mod; } }; using modint = MontgomeryModInt< mod >; struct UnionFind { vector< int > data; UnionFind() = default; explicit UnionFind(size_t sz) : data(sz, -1) {} bool unite(int x, int y) { x = find(x), y = find(y); if(x == y) return false; if(data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } int find(int k) { if(data[k] < 0) return (k); return data[k] = find(data[k]); } int size(int k) { return -data[find(k)]; } bool same(int x, int y) { return find(x) == find(y); } vector< vector< int > > groups() { int n = (int) data.size(); vector< vector< int > > ret(n); for(int i = 0; i < n; i++) { ret[find(i)].emplace_back(i); } ret.erase(remove_if(begin(ret), end(ret), [&](const vector< int > &v) { return v.empty(); }), end(ret)); return ret; } }; int main() { int H, W; cin >> H >> W; vector A(H, vector< int >(W)); for (auto &xs: A) { for (auto &x: xs) cin >> x; } using pi = pair< int, int >; vector< pi > vs; vs.reserve(H * W); for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { vs.emplace_back(i, j); } } sort(vs.begin(), vs.end(), [&](auto &p, auto &q) { return A[p.first][p.second] > A[q.first][q.second]; }); vector< modint > mul2(H + W); mul2[0] = 1; for(int i = 1; i < H + W; i++) { mul2[i] = mul2[i - 1] + mul2[i - 1]; } UnionFind uf(H + W); int comp = H + W; modint ret = 0; for (auto [i, j]: vs) { if (uf.same(i, j + H)) { continue; } ret += mul2[comp - 2] * A[i][j]; uf.unite(i, j + H); --comp; } cout << ret << endl; }