Description:

Solution:

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

#define BASE 100000000

struct bigint

{

	int len,num[10];

	bigint(){len = 0;memset(num,0,sizeof(num));}

	int& operator [](int x){return num[x];}

	void print()

	{

		cout << num[len];

		for(int i = len - 1;i >= 1;--i)

		{

			if(num[i] < 10000000)putchar('0');

			if(num[i] < 1000000)putchar('0');

			if(num[i] < 100000)putchar('0');

			if(num[i] < 10000)putchar('0');

			if(num[i] < 1000)putchar('0');

			if(num[i] < 100)putchar('0');

			if(num[i] < 10)putchar('0');

			printf("%d",num[i]);

		}

		return;

	}

};

bigint operator + (bigint a,bigint b)

{

	if(a.len < b.len)swap(a,b);

	for(int i = 1;i <= b.len;++i)

	{

		a[i] += b[i];

		if(a[i] >= BASE)

		{

			a[i + 1] += 1;

			a[i] -= BASE;

		}

	}

	if(a[a.len + 1] > 0)++a.len;

	return a;

}

#define HASH 30007

#define STATE 300000

struct hash_map

{

	int lin[HASH],nxt[STATE],siz;

	ll dat[STATE];

	bigint f[STATE];

	void init(){siz = 0;memset(lin,0,sizeof(lin));}

	void add(ll sta,bigint ans)

	{

		int hsh = sta % HASH;

		for(int i = lin[hsh];i != 0;i = nxt[i])if(dat[i] == sta){f[i] = f[i] + ans;return;}

		++siz;dat[siz] = sta;f[siz] = ans;nxt[siz] = lin[hsh];lin[hsh] = siz;

		return;

	}

}h[2];

int n,m;

#define MAXL 50

int code[MAXL],code_[MAXL];

void decode(int *code,int m,ll sta)

{

	for(int i = m;i >= 0;--i)

	{

		code[i] = sta & 3;

		sta = sta >> 2;

	}

	return;

}

ll encode(int *code,int m)

{

	ll sta = 0;

	for(int i = 0;i <= m;++i)

	{

		sta = sta << 2;

		sta |= code[i];

	}

	return sta;

}

void shift(int *code,int *code_,bool tag)

{

	if(tag)

	{

		for(int i = m;i > 0;--i)code_[i] = code[i - 1];

		code_[0] = 0;

	}

	else

	{

		for(int i = m;i >= 0;--i)code_[i] = code[i];

	}

	return;

}

void dp(int i,int j,int cur)

{

	bool flag;

	if(j == m)flag = true;

	else flag = false;

	int left,up;

	for(int k = 1;k <= h[cur].siz;++k)

	{

		decode(code,m,h[cur].dat[k]);

		left = code[j - 1];up = code[j];

		if(left == 0 && up == 0)

		{

			if(i < n && j < m)

			{

				code[j - 1] = 1;code[j] = 2;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

		}

		if((left != 0 && up == 0) || (left == 0 && up != 0))

		{

			int t;

			if(left != 0)t = left;

			else t = up;

			if(i < n)

			{

				code[j - 1] = t;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

			if(j < m)

			{

				code[j - 1] = 0;code[j] = t;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

		}

		if(left != 0 && up != 0)

		{

			if(left == 1 && up == 1)

			{

				int t;

				int cnt = 0;

				for(t = j + 1;t <= m;++t)

				{

					if(code[t] == 1)++cnt;

					if(code[t] == 2)

					{

						if(cnt == 0){code[t] = 1;break;}

						else --cnt;

					}

				}

				code[j - 1] = 0;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				code[t] = 2;

			}

			if(left == 2 && up == 2)

			{

				int t;

				int cnt = 0;

				for(t = j - 2;t >= 0;--t)

				{

					if(code[t] == 2)++cnt;

					if(code[t] == 1)

					{

						if(cnt == 0){code[t] = 2;break;}

						else --cnt;

					}

				}

				code[j - 1] = 0;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				code[t] = 1;

			}

			if(left == 2 && up == 1)

			{

				code[j - 1] = 0;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

			if(left == 1 && up == 2)

			{

				bool tag = true;

				for(int t = 0;t <= j - 2;++t)if(code[t] != 0)tag = false;

				for(int t = j + 1;t <= m;++t)if(code[t] != 0)tag = false;

				if(tag && i == n && j == m)

				{

					code[j - 1] = 0;code[j] = 0;

					shift(code,code_,flag);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

				}

			}

		}

	}

}

void solve()

{

	int cur = 0;

	h[cur].init();

	bigint t;t[1] = 1;t.len = 1;

	h[cur].add(0,t);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			h[cur ^ 1].init();

			dp(i,j,cur);

			cur ^= 1;

		}

	}

	bigint res; 

	for(int i = h[cur].lin[0];i != 0;i = h[cur].nxt[i])

	{

		if(h[cur].dat[i] == 0)

		{

			res = h[cur].f[i];

			break;

		}

	}

	for(int i = 1;i <= res.len;++i)

	{

		res[i] = res[i] * 2;

	}

	for(int i = 1;i <= res.len;++i)

	{

		res[i + 1] += res[i] / BASE;

		res[i] %= BASE;

	}

	if(res[res.len + 1] > 0)

	{

		++res.len;

	}

	res.print();

	return;

}

int main()

{

	cin >> m >> n;

	if(m == 1 || n == 1)

	{

		cout << 1 << endl;

		return 0;

	}

	solve();

	return 0;

}