#ifndef __BINARY_MATRIX_H__
#define __BINARY_MATRIX_H__

#include <vector>
#include <functional>
#include <iostream>
#include <initializer_list>
#include <iterator>

class BinaryMatrixBoolReference {
	uint64_t& var_m;
	uint64_t mask_m;

public:
	BinaryMatrixBoolReference(const BinaryMatrixBoolReference&) = default;
	BinaryMatrixBoolReference(uint64_t& var, int bit);

	BinaryMatrixBoolReference& operator=(bool value);
	BinaryMatrixBoolReference& operator|=(bool value);
	BinaryMatrixBoolReference& operator&=(bool value);
	BinaryMatrixBoolReference& operator^=(bool value);

	operator bool() const;

	void Flip();
	void Swap(BinaryMatrixBoolReference& other);
};

void swap(BinaryMatrixBoolReference& left, BinaryMatrixBoolReference& right);

class BinaryMatrixRowConstIterator {
	static const int BITS = 64;
	
public:
	using iterator_category = std::random_access_iterator_tag;
	using difference_type = int64_t;
	using value_type = bool;
	using reference = bool;
	using pointer = bool*;

protected:
	uint64_t* ptr_m;
	int64_t offset_m;

public:
	BinaryMatrixRowConstIterator() = default;
	BinaryMatrixRowConstIterator(const uint64_t* ptr, int64_t offset);
	BinaryMatrixRowConstIterator(const BinaryMatrixRowConstIterator&) = default;
	BinaryMatrixRowConstIterator& operator=(const BinaryMatrixRowConstIterator&) = default;

	reference operator*() const;
	reference operator->() const;
	reference operator[](difference_type offset) const;

	BinaryMatrixRowConstIterator& operator++();
	BinaryMatrixRowConstIterator& operator--();
	BinaryMatrixRowConstIterator operator++(int);
	BinaryMatrixRowConstIterator operator--(int);

	BinaryMatrixRowConstIterator& operator+=(difference_type offset);
	BinaryMatrixRowConstIterator& operator-=(difference_type offset);

	static int Compare(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right);
};

bool operator==(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right);
bool operator!=(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right);
bool operator<(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right);
bool operator<=(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right);
bool operator>(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right);
bool operator>=(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right);

BinaryMatrixRowConstIterator operator+(const BinaryMatrixRowConstIterator& itr, int offset);
BinaryMatrixRowConstIterator operator+(int offset, const BinaryMatrixRowConstIterator& itr);
BinaryMatrixRowConstIterator operator-(const BinaryMatrixRowConstIterator& itr, int offset);


class BinaryMatrixRowIterator : public BinaryMatrixRowConstIterator {
	using Base = BinaryMatrixRowConstIterator;
	static const int BITS = 64;

public:
	using iterator_category = std::random_access_iterator_tag;
	using difference_type = std::ptrdiff_t;
	using value_type = bool;
	using reference = BinaryMatrixBoolReference;
	using pointer = BinaryMatrixBoolReference*;

	BinaryMatrixRowIterator() = default;
	BinaryMatrixRowIterator(uint64_t* ptr, int64_t offset);
	BinaryMatrixRowIterator(const BinaryMatrixRowIterator&) = default;
	BinaryMatrixRowIterator& operator=(const BinaryMatrixRowIterator&) = default;

	reference operator*() const;
	reference operator->() const;
	reference operator[](int offset) const;

	BinaryMatrixRowIterator& operator++();
	BinaryMatrixRowIterator& operator--();
	BinaryMatrixRowIterator operator++(int);
	BinaryMatrixRowIterator operator--(int);

	BinaryMatrixRowIterator& operator+=(difference_type offset);
	BinaryMatrixRowIterator& operator-=(difference_type offset);
};

BinaryMatrixRowIterator operator+(const BinaryMatrixRowIterator& itr, int offset);
BinaryMatrixRowIterator operator+(int offset, const BinaryMatrixRowIterator& itr);
BinaryMatrixRowIterator operator-(const BinaryMatrixRowIterator& itr, int offset);


class BinaryMatrixRow {
	using Reference = BinaryMatrixBoolReference;
	using Iterator = BinaryMatrixRowIterator;
	using ConstIterator = BinaryMatrixRowConstIterator;
	static const int BITS = 64;

	int size_m = 0;
	std::vector<uint64_t> arr_m;
public:
	BinaryMatrixRow() = default;
	BinaryMatrixRow(int size);
	BinaryMatrixRow(const BinaryMatrixRow&) = default;
	BinaryMatrixRow(BinaryMatrixRow&&) = default;

	BinaryMatrixRow& operator=(const BinaryMatrixRow&) = default;
	BinaryMatrixRow& operator=(BinaryMatrixRow&&) = default;

	BinaryMatrixRow& operator+=(const BinaryMatrixRow& right);
	
	Reference operator[](int index);
	bool operator[](int index) const;

	int Size() const;
	void Clear();
	void Flip();

	Iterator begin();
	Iterator end();
	ConstIterator begin() const;
	ConstIterator end() const;

private:
	static int Popcount(uint64_t value);
public:
	int Count() const;

	static int Compare(const BinaryMatrixRow& left, const BinaryMatrixRow& right);
};

bool operator==(const BinaryMatrixRow& left, const BinaryMatrixRow& right);
bool operator!=(const BinaryMatrixRow& left, const BinaryMatrixRow& right);
bool operator<(const BinaryMatrixRow& left, const BinaryMatrixRow& right);
bool operator<=(const BinaryMatrixRow& left, const BinaryMatrixRow& right);
bool operator>(const BinaryMatrixRow& left, const BinaryMatrixRow& right);
bool operator>=(const BinaryMatrixRow& left, const BinaryMatrixRow& right);
BinaryMatrixRow operator+(const BinaryMatrixRow& left, const BinaryMatrixRow& right);


class BinaryMatrix {
public:
	using Row = BinaryMatrixRow;
	using Iterator = std::vector<Row>::iterator;
	using ConstIterator = std::vector<Row>::const_iterator;

private:
	int height_m = 0;
	int width_m = 0;
	std::vector<Row> mat_m;

public:
	BinaryMatrix() = default;
	BinaryMatrix(int height, int width);
	BinaryMatrix(int height, int width, const std::function<bool(int, int)>& func);
	BinaryMatrix(const std::initializer_list<std::initializer_list<bool>>& lists);
	
	BinaryMatrix(const BinaryMatrix&) = default;
	BinaryMatrix(BinaryMatrix&&) = default;

	BinaryMatrix& operator=(const BinaryMatrix&) = default;
	BinaryMatrix& operator=(BinaryMatrix&&) = default;

	BinaryMatrixRow& operator[](int index);
	const BinaryMatrixRow& operator[](int index) const;

	const BinaryMatrix& operator+() const;
	const BinaryMatrix& operator-() const;

	BinaryMatrix& operator+=(const BinaryMatrix& right);
	BinaryMatrix& operator-=(const BinaryMatrix& right);
	BinaryMatrix& operator*=(const BinaryMatrix& right);
	BinaryMatrix& operator*=(bool scalar);

	Iterator begin();
	Iterator end();
	ConstIterator begin() const;
	ConstIterator end() const;

	int Height() const;
	int Width() const;
	bool Is_square() const;

	BinaryMatrix Trans() const;
	BinaryMatrix Inverse() const;
	bool Determinant() const;
	int Rank() const;
	BinaryMatrix Block(int top, int bottom, int left, int right) const;

	static bool Is_addable(const BinaryMatrix& left, const BinaryMatrix& right);
	static bool Is_multipliable(const BinaryMatrix& left, const BinaryMatrix& right);

	static int Compare(const BinaryMatrix& left, const BinaryMatrix& right);
	static BinaryMatrix Multiply(const BinaryMatrix& left, const BinaryMatrix& right);

	static BinaryMatrix Identity(int size);
	static BinaryMatrix Join_horizontally(const BinaryMatrix& left, const BinaryMatrix& right);
	static BinaryMatrix Join_vertically(const BinaryMatrix& top, const BinaryMatrix& bottom);
};

bool operator==(const BinaryMatrix& left, const BinaryMatrix& right);
bool operator!=(const BinaryMatrix& left, const BinaryMatrix& right);
bool operator<(const BinaryMatrix& left, const BinaryMatrix& right);
bool operator<=(const BinaryMatrix& left, const BinaryMatrix& right);
bool operator>(const BinaryMatrix& left, const BinaryMatrix& right);
bool operator>=(const BinaryMatrix& left, const BinaryMatrix& right);

BinaryMatrix operator+(const BinaryMatrix& left, const BinaryMatrix& right);
BinaryMatrix operator-(const BinaryMatrix& left, const BinaryMatrix& right);
BinaryMatrix operator*(const BinaryMatrix& left, const BinaryMatrix& right);
BinaryMatrix operator*(const BinaryMatrix& matrix, bool scalar);
BinaryMatrix operator*(bool scalar, const BinaryMatrix& matrix);

std::ostream& operator<<(std::ostream& ost, const BinaryMatrix& matrix);

struct BinaryMatrixReductionInfo {
	BinaryMatrix matrix;
	int rank;
	bool determinant;
};

BinaryMatrixReductionInfo Reduce_by_gauss(const BinaryMatrix& mat_arg, int row_max = -1);

#endif

#ifdef ONLY_MY_ENVIR
#include "BinaryMatrix.h"
#endif

#ifdef _MSC_VER
#include <intrin.h>
#endif

#include <algorithm>
#include <cassert>

/*-----------------------------------------*/
/*----   BinaryMatrixRowConstIterator   ---*/
/*-----------------------------------------*/

BinaryMatrixRowConstIterator::BinaryMatrixRowConstIterator(const uint64_t* ptr, int64_t offset)
	: ptr_m(const_cast<uint64_t*>(ptr)), offset_m(offset) {
}

BinaryMatrixRowConstIterator::reference BinaryMatrixRowConstIterator::operator*() const {
	int pos = offset_m / BITS;
	int bit = offset_m % BITS;
	return ptr_m[pos] & ((uint64_t)1 << bit);
}

BinaryMatrixRowConstIterator::reference BinaryMatrixRowConstIterator::operator->() const {
	return *(*this);
}

BinaryMatrixRowConstIterator::reference BinaryMatrixRowConstIterator::operator[](difference_type offset) const {
	return *(*this + offset);
}

BinaryMatrixRowConstIterator& BinaryMatrixRowConstIterator::operator++() {
	++offset_m;
	return *this;
}

BinaryMatrixRowConstIterator& BinaryMatrixRowConstIterator::operator--() {
	--offset_m;
	return *this;
}

BinaryMatrixRowConstIterator BinaryMatrixRowConstIterator::operator++(int) {
	BinaryMatrixRowConstIterator preserved(*this);
	++(*this);
	return preserved;
}

BinaryMatrixRowConstIterator BinaryMatrixRowConstIterator::operator--(int) {
	BinaryMatrixRowConstIterator preserved(*this);
	--(*this);
	return preserved;
}

BinaryMatrixRowConstIterator& BinaryMatrixRowConstIterator::operator+=(difference_type offset) {
	offset_m += offset;
	return *this;
}

BinaryMatrixRowConstIterator& BinaryMatrixRowConstIterator::operator-=(difference_type offset) {
	offset_m -= offset;
	return *this;
}

int BinaryMatrixRowConstIterator::Compare(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right) {
	assert(left.ptr_m == right.ptr_m);

	if (left.offset_m < right.offset_m) return -1;
	if (left.offset_m > right.offset_m) return 1;
	return 0;
}

bool operator==(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right) {
	return BinaryMatrixRowConstIterator::Compare(left, right) == 0;
}

bool operator!=(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right) {
	return BinaryMatrixRowConstIterator::Compare(left, right) != 0;
}

bool operator<(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right) {
	return BinaryMatrixRowConstIterator::Compare(left, right) < 0;
}

bool operator<=(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right) {
	return BinaryMatrixRowConstIterator::Compare(left, right) <= 0;
}

bool operator>(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right) {
	return BinaryMatrixRowConstIterator::Compare(left, right) > 0;
}

bool operator>=(const BinaryMatrixRowConstIterator& left, const BinaryMatrixRowConstIterator& right) {
	return BinaryMatrixRowConstIterator::Compare(left, right) >= 0;
}

BinaryMatrixRowConstIterator operator+(const BinaryMatrixRowConstIterator& itr, int offset) {
	BinaryMatrixRowConstIterator ret(itr);
	ret += offset;
	return ret;
}

BinaryMatrixRowConstIterator operator+(int offset, const BinaryMatrixRowConstIterator& itr) {
	BinaryMatrixRowConstIterator ret(itr);
	ret += offset;
	return ret;
}

BinaryMatrixRowConstIterator operator-(const BinaryMatrixRowConstIterator& itr, int offset) {
	BinaryMatrixRowConstIterator ret(itr);
	ret -= offset;
	return ret;
}

/*-----------------------------------------*/
/*------   BinaryMatrixRowIterator   ------*/
/*-----------------------------------------*/

BinaryMatrixRowIterator::BinaryMatrixRowIterator(uint64_t* ptr, int64_t offset) 
	: Base(ptr, offset) {
}

BinaryMatrixRowIterator::reference BinaryMatrixRowIterator::operator*() const {
	int pos = offset_m / BITS;
	int bit = offset_m % BITS;
	return reference(ptr_m[pos], bit);
}

BinaryMatrixRowIterator::reference BinaryMatrixRowIterator::operator->() const {
	return *(*this);
}

BinaryMatrixRowIterator::reference BinaryMatrixRowIterator::operator[](int offset) const {
	return *(*this + offset);
}

BinaryMatrixRowIterator& BinaryMatrixRowIterator::operator++() {
	Base::operator++();
	return *this;
}

BinaryMatrixRowIterator& BinaryMatrixRowIterator::operator--() {
	Base::operator--();
	return *this;
}

BinaryMatrixRowIterator BinaryMatrixRowIterator::operator++(int) {
	BinaryMatrixRowIterator preserved(*this);
	++(*this);
	return preserved;
}

BinaryMatrixRowIterator BinaryMatrixRowIterator::operator--(int) {
	BinaryMatrixRowIterator preserved(*this);
	--(*this);
	return preserved;
}

BinaryMatrixRowIterator& BinaryMatrixRowIterator::operator+=(difference_type offset) {
	Base::operator+=(offset);
	return *this;
}

BinaryMatrixRowIterator& BinaryMatrixRowIterator::operator-=(difference_type offset) {
	Base::operator-=(offset);
	return *this;
}

BinaryMatrixRowIterator operator+(const BinaryMatrixRowIterator& itr, int offset) {
	BinaryMatrixRowIterator ret(itr);
	ret += offset;
	return ret;
}

BinaryMatrixRowIterator operator+(int offset, const BinaryMatrixRowIterator& itr) {
	BinaryMatrixRowIterator ret(itr);
	ret += offset;
	return ret;
}

BinaryMatrixRowIterator operator-(const BinaryMatrixRowIterator& itr, int offset) {
	BinaryMatrixRowIterator ret(itr);
	ret -= offset;
	return ret;
}

/*-----------------------------------------*/
/*-----   BinaryMatrixBoolReference   -----*/
/*-----------------------------------------*/

BinaryMatrixBoolReference::BinaryMatrixBoolReference(uint64_t& var, int bit)
	: var_m(var), mask_m((uint64_t)1 << bit) {
}

BinaryMatrixBoolReference& BinaryMatrixBoolReference::operator=(bool value) {
	if (value) {
		var_m |= mask_m;
	} else {
		var_m &= ~mask_m;
	}
	return *this;
}

BinaryMatrixBoolReference& BinaryMatrixBoolReference::operator|=(bool value) {
	if (value) {
		var_m |= mask_m;
	}
	return *this;
}

BinaryMatrixBoolReference& BinaryMatrixBoolReference::operator&=(bool value) {
	if (!value) {
		var_m &= ~mask_m;
	}
	return *this;
}

BinaryMatrixBoolReference& BinaryMatrixBoolReference::operator^=(bool value) {
	if (value) {
		var_m ^= mask_m;
	}
	return *this;
}

BinaryMatrixBoolReference::operator bool() const {
	return var_m & mask_m;
}

void BinaryMatrixBoolReference::Flip() {
	var_m ^= mask_m;
}

void BinaryMatrixBoolReference::Swap(BinaryMatrixBoolReference& other) {
	if (*this == other) return;
	Flip();
	other.Flip();
}

void swap(BinaryMatrixBoolReference& left, BinaryMatrixBoolReference& right) {
	left.Swap(right);
}

/*-----------------------------------------*/
/*----------   BinaryMatrixRow   ----------*/
/*-----------------------------------------*/

BinaryMatrixRow::BinaryMatrixRow(int size) 
	: size_m(size), arr_m((size + BITS - 1) / BITS) {
}

BinaryMatrixRow& BinaryMatrixRow::operator+=(const BinaryMatrixRow& right) {
	assert(size_m == right.size_m);

	for (int i = 0; i < arr_m.size(); ++i) {
		arr_m[i] ^= right.arr_m[i];
	}
	return *this;
}

BinaryMatrixRow::Reference BinaryMatrixRow::operator[](int index) {
	int pos = index / BITS;
	int bit = index % BITS;
	return Reference(arr_m[pos], bit);
}

bool BinaryMatrixRow::operator[](int index) const {
	int pos = index / BITS;
	int bit = index % BITS;
	return arr_m[pos]& ((uint64_t)1 << bit);
}

int BinaryMatrixRow::Size() const {
	return size_m;
}

void BinaryMatrixRow::Clear() {
	std::fill(arr_m.begin(), arr_m.end(), 0);
}

void BinaryMatrixRow::Flip() {
	for (uint64_t& value : arr_m) {
		value = ~value;
	}

	// 使用していない領域は 0 にする
	int rest_bit = size_m % BITS;
	if (rest_bit == 0) return;

	uint64_t mask = ((uint64_t)1 << rest_bit) - 1;
	arr_m.back() &= mask;
}

BinaryMatrixRow::Iterator BinaryMatrixRow::begin() {
	return Iterator(arr_m.data(), 0);
}

BinaryMatrixRow::Iterator BinaryMatrixRow::end() {
	return Iterator(arr_m.data(), size_m);
}

BinaryMatrixRow::ConstIterator BinaryMatrixRow::begin() const {
	return ConstIterator(arr_m.data(), 0);
}

BinaryMatrixRow::ConstIterator BinaryMatrixRow::end() const {
	return ConstIterator(arr_m.data(), size_m);
}

int BinaryMatrixRow::Popcount(uint64_t value) {
#ifdef _MSC_VER
	return __popcnt64(value);
#elif defined(__GNUC__)
	return __builtin_popcountll(value);
#else
	value = (value & 0x5555555555555555) + ((value >> 1) & 0x5555555555555555);
	value = (value & 0x3333333333333333) + ((value >> 2) & 0x3333333333333333);
	value = (value & 0x0f0f0f0f0f0f0f0f) + ((value >> 4) & 0x0f0f0f0f0f0f0f0f);
	value = (value & 0x00ff00ff00ff00ff) + ((value >> 8) & 0x00ff00ff00ff00ff);
	value = (value & 0x0000ffff0000ffff) + ((value >> 16) & 0x0000ffff0000ffff);
	value = (value & 0x00000000ffffffff) + ((value >> 32) & 0x00000000ffffffff);
	return value;
#endif
}

int BinaryMatrixRow::Count() const {
	int sum = 0;
	for (int64_t value : arr_m) {
		sum += Popcount(value);
	}
	return sum;
}

/* 注意: 辞書順ではない(bit を下位から使用しているため) */
int BinaryMatrixRow::Compare(const BinaryMatrixRow& left, const BinaryMatrixRow& right) {
	if (left.size_m < right.size_m) return -1;
	if (left.size_m > right.size_m) return 1;

	const int N = left.arr_m.size();
	for (int i = 0; i < N; ++i) {
		if (left.arr_m[i] < right.arr_m[i]) return -1;
		if (left.arr_m[i] > right.arr_m[i]) return 1;
	}
	return 0;
}

bool operator==(const BinaryMatrixRow& left, const BinaryMatrixRow& right) {
	return BinaryMatrixRow::Compare(left, right) == 0;
}

bool operator!=(const BinaryMatrixRow& left, const BinaryMatrixRow& right) {
	return BinaryMatrixRow::Compare(left, right) != 0;
}

bool operator<(const BinaryMatrixRow& left, const BinaryMatrixRow& right) {
	return BinaryMatrixRow::Compare(left, right) < 0;
}

bool operator<=(const BinaryMatrixRow& left, const BinaryMatrixRow& right) {
	return BinaryMatrixRow::Compare(left, right) <= 0;
}

bool operator>(const BinaryMatrixRow& left, const BinaryMatrixRow& right) {
	return BinaryMatrixRow::Compare(left, right) > 0;
}

bool operator>=(const BinaryMatrixRow& left, const BinaryMatrixRow& right) {
	return BinaryMatrixRow::Compare(left, right) >= 0;
}

BinaryMatrixRow operator+(const BinaryMatrixRow& left, const BinaryMatrixRow& right) {
	BinaryMatrixRow ret(left);
	ret += right;
	return ret;
}

/*-----------------------------------------*/
/*------------   BinaryMatrix   -----------*/
/*-----------------------------------------*/

BinaryMatrix::BinaryMatrix(int height, int width) 
	: height_m(height), width_m(width), mat_m(height, Row(width)) {
}

BinaryMatrix::BinaryMatrix(int height, int width, const std::function<bool(int, int)>& func)
	: BinaryMatrix(height, width) {

	for (int i = 0; i < height_m; ++i) {
		for (int j = 0; j < width_m; ++j) {
			mat_m[i][j] = func(i, j);
		}
	}
}

BinaryMatrix::BinaryMatrix(const std::initializer_list<std::initializer_list<bool>>& lists) {
	int height = lists.size();
	int width = 0;
	for (const auto& list : lists) {
		width = std::max<int>(width, list.size());
	}

	*this = BinaryMatrix(height, width);

	int i = 0;
	for (const auto& list : lists) {
		int j = 0;
		for (bool value : list) {
			mat_m[i][j] = value;
			++j;
		}
		++i;
	}
}

BinaryMatrixRow& BinaryMatrix::operator[](int index) {
	return mat_m[index];
}

const BinaryMatrixRow& BinaryMatrix::operator[](int index) const {
	return mat_m[index];
}

const BinaryMatrix& BinaryMatrix::operator+() const {
	return *this;
}

const BinaryMatrix& BinaryMatrix::operator-() const {
	return *this;
}

BinaryMatrix& BinaryMatrix::operator+=(const BinaryMatrix& right) {
	assert(Is_addable(*this, right));
	
	for (int i = 0; i < height_m; ++i) {
		mat_m[i] += right.mat_m[i];
	}
	return *this;
}

BinaryMatrix& BinaryMatrix::operator-=(const BinaryMatrix& right) {
	*this += right;
	return *this;
}

BinaryMatrix& BinaryMatrix::operator*=(const BinaryMatrix& right) {
	assert(Is_multipliable(*this, right));

	*this = Multiply(*this, right);
	return *this;
}

BinaryMatrix& BinaryMatrix::operator*=(bool scalar) {
	if (!scalar) {
		for (Row& row : mat_m) {
			row.Clear();
		}
	}
	return *this;
}

BinaryMatrix::Iterator BinaryMatrix::begin() {
	return mat_m.begin();
}

BinaryMatrix::Iterator BinaryMatrix::end() {
	return mat_m.end();
}

BinaryMatrix::ConstIterator BinaryMatrix::begin() const {
	return mat_m.begin();
}

BinaryMatrix::ConstIterator BinaryMatrix::end() const {
	return mat_m.end();
}

int BinaryMatrix::Height() const {
	return height_m;
}

int BinaryMatrix::Width() const {
	return width_m;
}

bool BinaryMatrix::Is_square() const {
	return height_m == width_m;
}

BinaryMatrix BinaryMatrix::Trans() const {
	BinaryMatrix ret(width_m, height_m);

	for (int i = 0; i < height_m; ++i) {
		for (int j = 0; j < width_m; ++j) {
			ret.mat_m[j][i] = mat_m[i][j];
		}
	}
	
	return ret;
}

/* これより計算量の良い方法はある？ */
BinaryMatrix BinaryMatrix::Inverse() const {
	assert(Is_square());

	const int size = height_m;
	BinaryMatrix extended = Join_horizontally(*this, BinaryMatrix::Identity(size));
	const auto& res = Reduce_by_gauss(extended, size);

	if (res.rank < size) throw std::runtime_error("matrix not invertible");
	return res.matrix.Block(0, size, size, 2 * size);
}

bool BinaryMatrix::Determinant() const {
	assert(Is_square());

	const auto& res = Reduce_by_gauss(*this);
	return res.determinant;
}

int BinaryMatrix::Rank() const {
	const auto& res = Reduce_by_gauss(*this);
	return res.rank;
}

/* 要高速化 */
BinaryMatrix BinaryMatrix::Block(int top, int bottom, int left, int right) const {
	BinaryMatrix ret(bottom - top, right - left);

	for (int i = top; i < bottom; ++i) {
		for (int j = left; j < right; ++j) {
			ret.mat_m[i - top][j - left] = mat_m[i][j];
		}
	}
	return ret;
}

bool BinaryMatrix::Is_addable(const BinaryMatrix& left, const BinaryMatrix& right) {
	return left.height_m == right.height_m && left.width_m == right.width_m;
}

bool BinaryMatrix::Is_multipliable(const BinaryMatrix& left, const BinaryMatrix& right) {
	return left.width_m == right.height_m;
}

/* 注意: 辞書順ではない(bit を下位から使用しているため) */
int BinaryMatrix::Compare(const BinaryMatrix& left, const BinaryMatrix& right) {
	if (left.height_m < right.height_m) return -1;
	if (left.height_m > right.height_m) return 1;
	if (left.width_m < right.width_m) return -1;
	if (left.width_m > right.width_m) return 1;

	const int M = left.height_m;
	for (int i = 0; i < M; ++i) {
		int res_comp = BinaryMatrixRow::Compare(left.mat_m[i], right.mat_m[i]);
		if (res_comp != 0) return res_comp;
	}
	return 0;
}

BinaryMatrix BinaryMatrix::Multiply(const BinaryMatrix& left, const BinaryMatrix& right) {
	assert(Is_multipliable(left, right));
	
	const int L = left.height_m;
	const int M = left.width_m;
	const int N = right.width_m;

	BinaryMatrix ret(L, N);

	const BinaryMatrix tr = right.Trans();
	for (int i = 0; i < L; ++i) {
		for (int j = 0; j < N; ++j) {
			ret.mat_m[i][j] = (left.mat_m[i] + right.mat_m[j]).Count() % 2;
		}
	}

	return ret;
}

BinaryMatrix BinaryMatrix::Identity(int size) {
	BinaryMatrix ret(size, size);

	for (int i = 0; i < size; ++i) {
		ret.mat_m[i][i] = 1;
	}
	return ret;
}

/* 要高速化 */
BinaryMatrix BinaryMatrix::Join_horizontally(const BinaryMatrix& left, const BinaryMatrix& right) {
	assert(left.height_m == right.height_m);

	BinaryMatrix ret(left.height_m, left.width_m + right.width_m);

	for (int i = 0; i < left.height_m; ++i) {
		for (int j = 0; j < left.width_m; ++j) {
			ret.mat_m[i][j] = left.mat_m[i][j];
		}
	}

	for (int i = 0; i < right.height_m; ++i) {
		for (int j = 0; j < right.width_m; ++j) {
			ret.mat_m[i][j + left.width_m] = right.mat_m[i][j];
		}
	}

	return ret;
}

BinaryMatrix BinaryMatrix::Join_vertically(const BinaryMatrix& top, const BinaryMatrix& bottom) {
	assert(top.width_m == bottom.width_m);

	BinaryMatrix ret(top.height_m + bottom.height_m, top.width_m);

	for (int i = 0; i < top.height_m; ++i) {
		ret.mat_m[i] = top.mat_m[i];
	}

	for (int i = 0; i < bottom.height_m; ++i) {
		ret.mat_m[i + top.height_m] = bottom.mat_m[i];
	}

	return ret;
}

bool operator==(const BinaryMatrix& left, const BinaryMatrix& right) {
	return BinaryMatrix::Compare(left, right) == 0;
}

bool operator!=(const BinaryMatrix& left, const BinaryMatrix& right) {
	return BinaryMatrix::Compare(left, right) != 0;
}

bool operator<(const BinaryMatrix& left, const BinaryMatrix& right) {
	return BinaryMatrix::Compare(left, right) < 0;
}

bool operator<=(const BinaryMatrix& left, const BinaryMatrix& right) {
	return BinaryMatrix::Compare(left, right) <= 0;
}

bool operator>(const BinaryMatrix& left, const BinaryMatrix& right) {
	return BinaryMatrix::Compare(left, right) > 0;
}

bool operator>=(const BinaryMatrix& left, const BinaryMatrix& right) {
	return BinaryMatrix::Compare(left, right) >= 0;
}

BinaryMatrix operator+(const BinaryMatrix& left, const BinaryMatrix& right) {
	BinaryMatrix ret(left);
	ret += right;
	return ret;
}

BinaryMatrix operator-(const BinaryMatrix& left, const BinaryMatrix& right) {
	BinaryMatrix ret(left);
	ret -= right;
	return ret;
}

BinaryMatrix operator*(const BinaryMatrix& left, const BinaryMatrix& right) {
	return BinaryMatrix::Multiply(left, right);
}

BinaryMatrix operator*(const BinaryMatrix& matrix, bool scalar) {
	BinaryMatrix ret(matrix);
	ret *= scalar;
	return ret;
}

BinaryMatrix operator*(bool scalar, const BinaryMatrix& matrix) {
	BinaryMatrix ret(matrix);
	ret *= scalar;
	return ret;
}

std::ostream& operator<<(std::ostream& ost, const BinaryMatrix& matrix) {
	for (int i = 0; i < matrix.Height(); ++i) {
		for (int j = 0; j < matrix.Width(); ++j) {
			ost << matrix[i][j];
			if (j + 1 == matrix.Width()) {
				ost << std::endl;
			} else {
				ost << ' ';
			}
		}
	}
	return ost;
}


BinaryMatrixReductionInfo Reduce_by_gauss(const BinaryMatrix& mat_arg, int row_max) {
	BinaryMatrix mat = mat_arg;
	if (row_max == -1) {
		row_max = mat.Width();
	}

	const int M = mat.Height();
	const int N = mat.Width();

	int rank = 0;
	for (int row = 0; row < row_max; ++row) {
		/* ピボット選択 */
		int pivot_i = -1;
		for (int i = rank; i < M; ++i) {
			if (mat[i][row]) {
				pivot_i = i;
				break;
			}
		}

		/* 列 curr_j 内の値がすべて 0 なら飛ばす */
		if (pivot_i == -1) continue;

		/* 入れ替え */
		if (pivot_i != rank) {
			using std::swap;
			swap(mat[pivot_i], mat[rank]);		// 実装注意
		}

		/* 基本変形 */
		for (int i = 0; i < M; ++i) {
			if (i == rank) continue;
			if (!mat[i][row]) continue;

			mat[i] += mat[rank];
		}
		++rank;
	}

	BinaryMatrixReductionInfo ret;
	ret.matrix = std::move(mat);
	ret.rank = rank;
	ret.determinant = (rank == M);
	return ret;
}
#ifndef __INTMOD_H__0001__
#define __INTMOD_H__0001__

#include <vector>
#include <iostream>
#include <cassert>
#include <iostream>

/* Modulus must be less than 0x80000000, and must not be 0. */
template <uint32_t Modulus>
class IntMod {
	typedef int Int;
	typedef unsigned int UInt;
	typedef long long Long;
	typedef unsigned long long ULong;

public:
	template <uint32_t Modulus_>
	friend bool operator==(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator!=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator<(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator<=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator>(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator>=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);

private:
	UInt value_m;

public:
	IntMod() { value_m = 0; }
	IntMod(UInt value) { value_m = value % Modulus; }
	IntMod(ULong value) { value_m = value % Modulus; }
	IntMod(Int value) {
		Int tmp = value % (Int)Modulus;
		value_m = tmp >= 0 ? tmp : Modulus - (unsigned int)(-tmp);
	}
	IntMod(Long value) {
		Int tmp = value % (Long)Modulus;
		value_m = tmp >= 0 ? tmp : Modulus - (unsigned int)(-tmp);
	}
	IntMod(const IntMod& other) : value_m(other.value_m) {}
	IntMod& operator=(const IntMod& other) { value_m = other.value_m; return *this; }
	
	const IntMod& operator+() const { return *this; }
	IntMod operator-() const { return IntMod(Modulus - value_m); }
	IntMod& operator++() {
		++value_m;
		if (value_m == Modulus) value_m = 0;
		return *this;
	}
	IntMod& operator--() {
		if (value_m == 0) value_m = Modulus;
		--value_m;
		return *this;
	}
	IntMod operator++(int dummy) {
		IntMod tmp(*this);
		++(*this);
		return tmp;
	}
	IntMod operator--(int dummy) {
		IntMod tmp(*this);
		--(*this);
		return tmp;
	}
	IntMod& operator+=(const IntMod& right) {
		value_m += right.value_m;		// value_m < 0x80000000
		if (value_m >= Modulus) value_m -= Modulus;
		return *this;
	}
	IntMod& operator-=(const IntMod& right) {
		if (value_m < right.value_m) value_m += Modulus;
		value_m -= right.value_m;
		return *this;
	}
	IntMod& operator*=(const IntMod& right) {
		value_m = ((ULong)value_m * right.value_m) % Modulus;
		return *this;
	}	
	IntMod& operator/=(const IntMod& right) {
		(*this) *= (right.Inverse());
		return *this;
	}
	// for power
	IntMod operator[](ULong exp) const {
		return Pow(exp);
	}

	/* Modulus must be a prime. */
	IntMod Inverse() const { return (*this).Pow(Modulus - 2); }
	IntMod Pow(ULong exp) const {
		IntMod product = 1;
		IntMod factor(*this);
		while (exp > 0) {
			if (exp & 1) product *= factor;
			factor *= factor;
			exp >>= 1;
		}
		return product;
	}
	UInt Get_value() const {
		return value_m;
	}

	static IntMod Fact(UInt num) {
		static std::vector<IntMod> table(1, 1);
		if (table.size() > num) return table[num];

		int old_size = table.size();
		table.resize(num + 1);
		for (int i = old_size; i <= num; i++) {
			table[i] = table[i - 1] * i;
		}
		return table[num];
	}

	static IntMod Combi(UInt n, UInt r) {
		if (n < r) throw "okashii";
		return IntMod::Fact(n) / (IntMod::Fact(n - r) * IntMod::Fact(r));
	}

	static IntMod Permutation(UInt n, UInt r) {
		if (n < r) throw "okashii";
		return IntMod::Fact(n) / IntMod::Fact(n - r);
	}

	static std::vector<IntMod> Inverse_list(int size) {
		assert(size < Modulus);
		std::vector<IntMod> ret_arr(size + 1);
		ret_arr[1] = 1;
		for (int i = 2; i <= size; ++i) {
			ret_arr[i] = ((ULong)(Modulus - Modulus / i) * ret_arr[Modulus % i].Get_value()) % Modulus;
		}
		return ret_arr;
	}
};

template <uint32_t Modulus>
IntMod<Modulus> operator+(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret += right;
	return ret;
}

template <uint32_t Modulus>
IntMod<Modulus> operator-(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret -= right;
	return ret;
}

template <uint32_t Modulus>
IntMod<Modulus> operator*(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret *= right;
	return ret;
}

template <uint32_t Modulus>
IntMod<Modulus> operator/(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret /= right;
	return ret;
}


template <uint32_t Modulus>
bool operator==(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m == right.value_m; }
template <uint32_t Modulus>
bool operator!=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m != right.value_m; }
/* for set/map */
template <uint32_t Modulus>
bool operator<(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m < right.value_m; }
template <uint32_t Modulus>
bool operator<=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m <= right.value_m; }
template <uint32_t Modulus>
bool operator>(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m > right.value_m; }
template <uint32_t Modulus>
bool operator>=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m >= right.value_m; }

template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator+(const IntMod<Modulus>& left, Integer right) { return left + IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator+(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) + right; }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator-(const IntMod<Modulus>& left, Integer right) { return left - IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator-(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) - right; }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator*(const IntMod<Modulus>& left, Integer right) { return left * IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator*(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) * right; }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator/(const IntMod<Modulus>& left, Integer right) { return left / IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator/(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) / right; }

template <uint32_t Modulus>
std::istream& operator<<(std::istream& ist, const IntMod<Modulus>& val) {
	uint64_t tmp;
	ist >> tmp;
	val = tmp;
	return ist;
}

template <uint32_t Modulus>
std::ostream& operator<<(std::ostream& ost, const IntMod<Modulus>& val) {
	ost << val.Get_value();
	return ost;
}

typedef IntMod<1000000007> MInt;

#if 1
MInt operator"" _m(unsigned long long num) { return MInt(num); }
#endif

#endif

#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i, a, n) for(LL i = (a), i##_max = (n); i < i##_max; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##min = (a); i >= i##min; --i)
#define ALL(arr) (arr).begin(), (arr).end()
#define FLOAT fixed << setprecision(16)
#define SPEEDUP {cin.tie(NULL); ios::sync_with_stdio(false);}
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const string INFSTR = "\x7f";
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template<class T>
T Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }
template <class T>
T Next() { T buf; cin >> buf; return buf; }

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "UnionFind.h"
#include "Graph.h"
#include "Range.h"
#include "Global.h"
#include "FlowSolver.h"
#include "Tree.h"
#include "SuffixArray.h"
#include "Matrix.h"
#include "SegmentTree.h"
#include "SegmentTree2D.h"
#include "BIT.h"
#include "Rational.h"
#include "Position.h"
#include "Factorization.h"
#include "Math.h"
#include "LazySegmentTree.h"
#include "BinaryMatrix.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp;  ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

#if 1234567891
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
// template <class T>
// auto Is(const T& value) { return [value](const auto& comparand) -> bool { return comparand == value; }; }
#endif

using MK = IntMod<998244353>;

int N, M;
int main() {
	cin >> N >> M;
	
	BinaryMatrix mat(N, M);
	for (auto&& row : mat) {
		for (auto val : row) {
			val = Next<int>();
		}
	}

	int rank = mat.Rank();
	int rem = N + M - 2 * rank;
	cout << MK(2).Pow(rank + rem - 1) * (MK(2).Pow(rank) - 1) << endl;
	return 0;
}



Measured memory_bytes: 256