记录编号	218766	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 邮递员	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.048 s
提交时间	2016-01-11 11:11:13	内存使用	0.43 MiB

#define ll long long

#include <stdio.h>
#include <string.h>

const int Base=(int)(1e9);
int n,m;

inline int Max(int a,int b){return a>b?a:b;}

struct BigNum{
	#define MAXSIZE 5UL
	int s[MAXSIZE];
	BigNum(){clr();return;}
	inline void clr(){memset(s,0,sizeof(s));return;}
	inline void setnum(int x){clr();while(x) s[++s[0]]=x%Base,x/=Base;return;}
	inline void prx(){printf("%d",s[s[0]]);for(int i=s[0]-1;i>0;i--) printf("%09d",s[i]);return;}
	friend BigNum operator + (BigNum temp_a,BigNum temp_b){
		BigNum temp_c;int *a=temp_a.s,*b=temp_b.s,*c=temp_c.s;int i;
		for(c[0]=Max(a[0],b[0])+1,i=1;i<=c[0];i++) c[i]+=a[i]+b[i],c[i+1]+=c[i]/Base,c[i]%=Base;
		while(!c[c[0]]) --c[0];return temp_c;
	}
	void operator += (BigNum b){*this=*this+b;return;}
	void operator = (int t){setnum(t);return;}
}Ans;

struct HashTable{
	#define MAXHASH 2601L
	int key[MAXHASH];int cnt,hash[MAXHASH];BigNum val[MAXHASH];
	inline void clr(){cnt=0;memset(key,-1,sizeof(key));memset(hash,0,sizeof(hash));memset(val,0,sizeof(val));return;}
	inline void NewNode(int i,int key_){hash[i]=++cnt;key[cnt]=key_;return;}
	BigNum& operator [] (const int hash_){
		int k;
		for(int i=hash_%MAXHASH;;i++){
			if(i==MAXHASH) i=0;
			if(!hash[i]) NewNode(i,hash_);
			if(key[hash[i]]==hash_){k=hash[i];break;}
		}
		return val[k];
	}
}f[2];

inline void Change(int &t,int c,int r){int w=(c-1)<<1;t|=3<<w;t^=3<<w;t|=r<<w;return;}
inline int Get(int t,int c){return (t>>((c-1)<<1))&3;}
inline int Find(int t,int c){for(int i=c,b=0,rep=Get(t,c)==1?1:-1;;i+=rep){b+=Get(t,i)==1?1:-1;b+=Get(t,i)==0?1:0;if(b==0) return i;}return -1;}

inline void DP(int i,int j){
	int now=((i-1)*m+j)&1,last=now^1,tot=f[last].cnt;f[now].clr();
	for(int x=1,p,q;x<=tot;x++){
		int t=f[last].key[x];
		BigNum val=f[last].val[x];
		p=Get(t,j),q=Get(t,j+1);
		if(p==0&&q==0){if(i==n||j==m) continue;Change(t,j,1);Change(t,j+1,2);f[now][t]+=val;}
		else if(p>0&&q==0){if(i!=n) f[now][t]+=val;if(j!=m) Change(t,j,0),Change(t,j+1,p),f[now][t]+=val;}
		else if(p==0&&q>0){if(j!=m) f[now][t]+=val;if(i!=n) Change(t,j,q),Change(t,j+1,0),f[now][t]+=val;}
		else if(p==1&&q==1){Change(t,Find(t,j+1),1);Change(t,j,0);Change(t,j+1,0);f[now][t]+=val;}
		else if(p==2&&q==2){Change(t,Find(t,j),2);Change(t,j,0);Change(t,j+1,0);f[now][t]+=val;}
		else if(p==1&&q==2){if(i==n&&j==m) Ans+=val;}
		else if(p==2&&q==1){Change(t,j,0);Change(t,j+1,0);f[now][t]+=val;}
	}
	return;
}

int main(){
	freopen("postman.in","r",stdin);freopen("postman.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(n==1||m==1){puts("1");return 0;}
	if(n<m) n^=m,m^=n,n^=m;
	f[0].clr();f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) DP(i,j);
		if(i!=n) for(int k=1,R=f[(i*m)&1].cnt,c=(i*m)&1;k<=R;k++) f[c].key[k]<<=2;
	}
	Ans+=Ans;Ans.prx();
	return 0;
}