Language: C++


#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;

//?????°???????????????????????\??????mod??¢??°
inline long long imod(long long a, long long b)
{
	return (a >= 0) ? (a % b) : (a % b + b);
}

//mint????????°?????°?????????2??????
template <long long MOD> class mint;
template <long long MOD> mint<MOD> m_pow(mint<MOD> x, long long n);

//mod?????´??°?????????
template <long long MOD = 1000000007>
class mint
{
public:
	template<long long MOD>mint<MOD> operator+(const mint<MOD> &other)const
	{
		return mint<MOD>(imod(a + other.a, MOD));
	}
	template<long long MOD>mint<MOD> operator-(const mint<MOD> &other)const
	{
		return mint<MOD>(imod(a - other.a, MOD));
	}
	template<long long MOD>mint<MOD> operator*(const mint<MOD> &other)const
	{
		return mint<MOD>(imod(a * other.a, MOD));
	}
	template<long long MOD>mint<MOD> operator+=(const mint<MOD> &other)
	{
		a = imod(a + other.a, MOD);
		return mint<MOD>(a);
	}
	template<long long MOD>mint<MOD> operator-=(const mint<MOD> &other)
	{
		a = imod(a - other.a, MOD);
		return mint<MOD>(a);
	}
	template<long long MOD>mint<MOD> operator*=(const mint<MOD> &other)
	{
		a = imod(a * other.a, MOD);
		return mint<MOD>(a);
	}
	template<long long MOD>mint<MOD> operator+()const
	{
		return *this;
	}
	template<long long MOD>mint<MOD> operator-()const
	{
		return mint<MOD>(-a);
	}
	template<long long MOD>mint<MOD>& operator++()
	{
		*this += 1;
		return *this;
	}
	template<long long MOD>mint<MOD> operator++(int)
	{
		auto tmp = *this;
		*this += 1;
		return tmp;
	}
	template<long long MOD>mint<MOD>& operator--()
	{
		*this -= 1;
		return *this;
	}
	template<long long MOD>mint<MOD> operator--(int)
	{
		auto tmp = *this;
		*this -= 1;
		return tmp;
	}
	template<long long MOD>mint<MOD> operator~()const
	{
		return pow(a, e_phi - 1);
	}
	template<long long MOD>mint<MOD>& operator=(const mint<MOD> &other)
	{
		a = other.a;
		return *this;
	}
	operator long long()const
	{
		return a;
	}
	explicit operator int()const
	{
		return (int)a;
	}
	static long long getmod()
	{
		return mod;
	}
	mint(long long a_) :a(imod(a_, MOD))
	{
		//????????????
		static_assert(MOD >= 2, "MOD cannot be below 2.");

		if (e_phi > 0)return;
		//??????????????¢??°??(mod)????¨??????????
		e_phi = MOD;
		long long m_ = MOD;
		for (int i = 2; i * i <= m_; ++i)
		{
			if (m_ % i == 0)
			{
				e_phi = e_phi / i * (i - 1);
				for (; m_ % i == 0; m_ /= i);
			}
		}
		if (m_ != 1)e_phi = e_phi / m_ * (m_ - 1);
	}
	mint() :a(0) {}
private:
	static long long e_phi;
	long long a;
};

//mint????´????
//x^n????¨?????????????
template<long long MOD>mint<MOD> m_pow(mint<MOD> x, long long n)
{
	mint<MOD> res = 1;
	while (n > 0)
	{
		if (n & 1)res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}


//mint??????????¨????
//O(x)?¨???????????????????????????????
//?????¨?\¨??????????????§fact_set????¨??????????
template<long long MOD>mint<MOD> fact(mint<MOD> x)
{
	mint res(1);
	for (long long i = 1; i <= (long long)x; ++i)
	{
		res *= i;
	}
	return res;
}

//mint??????????¨????????????????
//set???????°????0???x?????§???????????°?????????????????????
//O(x)?¨???????????????????????????????
template<long long MOD>void fact_set(std::vector<mint<MOD>> &set, mint<MOD> x = mint<MOD>(-1))
{
	mint res(1);
	set.push_back(1);
	for (long long i = 1; i <= (long long)x; ++i)
	{
		res *= i;
		set.push_back(res);
	}
}

template<long long MOD>long long mint<MOD>::e_phi = -1;

//mint??????stream????????\????????????
template<long long MOD> std::ostream& operator<<(std::ostream& os, mint<MOD> i)
{
	os << (long long)i;
	return os;
}

template<long long MOD> std::istream& operator >> (std::istream& is, mint<MOD>& i)
{
	long long tmp;
	is >> tmp;
	i = tmp;
	return is;
}

typedef mint<100000> Int;

Int ans = 1;
int n, m;
char basestr[401];
int plane[400];

Int oldm[1 << 19][2];
Int memo[1 << 19][2];

Int pack_base;

Int wrap(int bs, int f)
{
	return oldm[bs][f] + oldm[bs + pack_base][f];
}

int main(void)
{
	cin >> m >> n;
	for (int k = 0; k < m; ++k)
	{
		scanf("%s", basestr + (k * n));
	}
	pack_base = m_pow(Int(2), n - 2);
	for (int i = 0; i < n * m; ++i)
	{
		switch (basestr[i])
		{
		case '?':plane[i] = 7; ans *= Int(3); break;
		case 'J':plane[i] = 1; break;
		case 'O':plane[i] = 2; break;
		case 'I':plane[i] = 4; break;
		}
	}
	Int maxst = m_pow(Int(2), n - 1);
	for (int bs = 0; bs < maxst; ++bs)
	{
		oldm[bs][0] = oldm[bs][1] = 0;
	}
	oldm[0][0] = 0;
	oldm[0][1] = 0;
	if (plane[0] & 1)oldm[0][1] += Int(1);
	if (plane[0] & 2)oldm[0][0] += Int(1);
	if (plane[0] & 4)oldm[0][0] += Int(1);

	for (int i = 1; i < n * m; ++i)
	{
		for (int bs = 0; bs < maxst; ++bs)
		{
			memo[bs][0] = memo[bs][1] = 0;
			if (plane[i] & 1)
			{
				if (bs % 2 == 0)memo[bs][1] += (wrap(bs / 2, 0) + wrap(bs / 2, 1));
			}
			if (plane[i] & 2)
			{
				if (bs % 2 == 1)memo[bs][0] += wrap(bs / 2, 1);
				if (bs % 2 == 0)memo[bs][0] += wrap(bs / 2, 0);
			}
			if (plane[i] & 4)
			{
				if (bs % 2 == 0)
				{
					memo[bs][0] += (oldm[bs / 2][0] + oldm[bs / 2][1]);
					if ((i + 1) % n == 0)
					{
						memo[bs][0] += (oldm[bs / 2 + pack_base][0] + oldm[bs / 2 + pack_base][1]);
					}
				}
			}
		}
		for (int bs = 0; bs < maxst; ++bs)
		{
			oldm[bs][0] = memo[bs][0];
			oldm[bs][1] = memo[bs][1];
		}
	}
	Int bad;
	for (int bs = 0; bs < maxst; ++bs)
	{
		bad += (oldm[bs][0] + oldm[bs][1]);
	}
	ans -= bad;
	cout << ans << endl;
	return 0;
}

Compiler output:
a.cc:37:18: error: declaration of template parameter 'MOD' shadows template parameter
   37 |         template<long long MOD>mint<MOD> operator+(const mint<MOD> &other)const
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:41:18: error: declaration of template parameter 'MOD' shadows template parameter
   41 |         template<long long MOD>mint<MOD> operator-(const mint<MOD> &other)const
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:45:18: error: declaration of template parameter 'MOD' shadows template parameter
   45 |         template<long long MOD>mint<MOD> operator*(const mint<MOD> &other)const
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:49:18: error: declaration of template parameter 'MOD' shadows template parameter
   49 |         template<long long MOD>mint<MOD> operator+=(const mint<MOD> &other)
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:54:18: error: declaration of template parameter 'MOD' shadows template parameter
   54 |         template<long long MOD>mint<MOD> operator-=(const mint<MOD> &other)
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:59:18: error: declaration of template parameter 'MOD' shadows template parameter
   59 |         template<long long MOD>mint<MOD> operator*=(const mint<MOD> &other)
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:64:18: error: declaration of template parameter 'MOD' shadows template parameter
   64 |         template<long long MOD>mint<MOD> operator+()const
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:68:18: error: declaration of template parameter 'MOD' shadows template parameter
   68 |         template<long long MOD>mint<MOD> operator-()const
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:72:18: error: declaration of template parameter 'MOD' shadows template parameter
   72 |         template<long long MOD>mint<MOD>& operator++()
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:77:18: error: declaration of template parameter 'MOD' shadows template parameter
   77 |         template<long long MOD>mint<MOD> operator++(int)
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:83:18: error: declaration of template parameter 'MOD' shadows template parameter
   83 |         template<long long MOD>mint<MOD>& operator--()
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:88:18: error: declaration of template parameter 'MOD' shadows template parameter
   88 |         template<long long MOD>mint<MOD> operator--(int)
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:94:18: error: declaration of template parameter 'MOD' shadows template parameter
   94 |         template<long long MOD>mint<MOD> operator~()const
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc:98:18: error: declaration of template parameter 'MOD' shadows template parameter
   98 |         template<long long MOD>mint<MOD>& operator=(const mint<MOD> &other)
      |                  ^~~~
a.cc:33:11: note: template parameter 'MOD' declared here
   33 | template <long long MOD = 1000000007>
      |           ^~~~
a.cc: In static member function 'static long long int mint<MOD>::getmod()':
a.cc:113:24: error: 'mod' was not declared in this scope; did you mean 'modf'?
  113 |                 return mod;
      |                        ^~~
      |                        modf