#include<cstdio>
long long int a[102][102],b[102][102],c[102][102],d[102][102];
int main()
{
	long long int w,h,i,j;
	scanf("%lld%lld",&w,&h);
	for(i=1;i<=100;i++)
	{
		b[1][i]=1;
		d[i][1]=1;
	}
	for(i=4;i<=100;i++)
	{
		for(j=2;j<=i-2;j++)
		{
			a[j][i-j]=d[j][i-j-1]%100000;
			b[j][i-j]=a[j][i-j-1]%100000+b[j][i-j-1]%100000;
			c[j][i-j]=b[j-1][i-j]%100000;
			d[j][i-j]=c[j-1][i-j]%100000+d[j-1][i-j]%100000;
		}
	}
	for(j=2;j<=99;j++)
		{
			a[j][101-j]=d[j][101-j-1]%100000;
			b[j][101-j]=a[j][101-j-1]%100000+b[j][101-j-1]%100000;
			c[j][101-j]=b[j-1][101-j]%100000;
			d[j][101-j]=c[j-1][101-j]%100000+d[j-1][101-j]%100000;
		}
	for(i=102;i<=200;i++)
	{
		for(j=i-100;j<=100;j++)
		{
			a[j][i-j]=d[j][i-j-1]%100000;
			b[j][i-j]=a[j][i-j-1]+b[j][i-j-1]%100000;
			c[j][i-j]=b[j-1][i-j]%100000;
			d[j][i-j]=c[j-1][i-j]%100000+d[j-1][i-j]%100000;
		}
	}
	printf("%lld",(a[w][h]+b[w][h]+c[w][h]+d[w][h])%100000);
	return 0;
}	

#include<stdio.h>
#define mod 100000

struct ROAD {
	int left;
	int up;
} road[110][110];

int main() {

	int w,h;
	int i,j;
	
	scanf("%d %d", &w, &h);
	for(i=1 ; i<=w ; i++)
		road[1][i].left=1;
	for(i=1 ; i<=h ; i++)
		road[i][1].up=1;

	for(i=2 ; i<=h ; i++) {
		for(j=2 ; j<=w ; j++) {
			road[i][j].left=road[i][j-1].left+road[i-1][j-1].up;
			road[i][j].up=road[i-1][j].up+road[i-1][j-1].left;
			road[i][j].left %= mod, road[i][j].up %= mod;
		}
	}

	printf("%d\n", (road[h][w].left+road[h][w].up)%mod);

	return 0;
}

#include <stdio.h>      //Dynamic Programming Solution

#define N 15
#define M 15

FILE *in=stdin;
FILE *out=stdout;

int n,m,map[N][M],ans,cnt,mat[30][30],dy[1200000][22];

struct data
{
	int x,y;
}a[30];

void process()
{
	int i,j,k,x;
	for(i=1;i<(1<<cnt);i++)
	{
		for(j=1;j<=cnt;j++)
		{
			if((i>>(j-1))&1)
			{
				x=i^(1<<(j-1));
				if(x==0)
				{
					if(mat[0][j]!=-1) dy[i][j]=1;
				}
				else
				{
					for(k=1;k<=cnt;k++)
					{
						if((x>>(k-1))&1 && mat[j][k]!=-1 && (mat[j][k]&x)==0) 
							dy[i][j]+=dy[x][k];
					}
				}
			}
		}
	}
	for(i=1;i<=cnt;i++)
	{
		if(mat[i][0]==0) 
			ans+=dy[(1<<cnt)-1][i];
	}
}

bool check_in(int l, int r, int t)
{
	if(l<r)
	{
		if(l<t && t<r) return true;
		return false;
	}
	if(r<t && t<l) return true;
	return false;
}

void get_house()
{
	int i,j,k;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(map[i][j]==1)
			{
				cnt++;
				a[cnt].y=i;
				a[cnt].x=j;
			}
			else if(map[i][j]==2)
			{
				a[0].y=i;
				a[0].x=j;
			}
		}
	}
	for(i=0;i<=cnt;i++)
	{
		for(j=i+1;j<=cnt;j++)
		{
			if(a[i].x!=a[j].x && a[i].y!=a[j].y) mat[i][j]=mat[j][i]=-1;
			if(a[i].x==a[j].x)
			{
				for(k=1;k<=cnt;k++)
				{
					if(a[k].x==a[i].x && check_in(a[i].y,a[j].y,a[k].y))
					{
						mat[i][j]|=(1<<(k-1));
						mat[j][i]|=(1<<(k-1));
					}
				}
			}
			else
			{
				for(k=1;k<=cnt;k++)
				{
					if(a[k].y==a[i].y && check_in(a[i].x,a[j].x,a[k].x))
					{
						mat[i][j]|=(1<<(k-1));
						mat[j][i]|=(1<<(k-1));
					}
				}
			}
		}
	}
}

int main()
{
	int i,j;
	fscanf(in,"%d %d",&m,&n);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++) fscanf(in,"%d",&map[i][j]);
	}
	get_house();
	process();
	fprintf(out,"%d",ans);
	fclose(in);
	fclose(out);
	return 0;
}

#include <stdio.h>
#include <vector>

struct pos{
	int x,y;
};

int n, m;
int map[12][12], numHouse, res;
bool chk[12][12];

pos church;
std::vector < pos > dir[5][12][12];

void fly(int x, int y, int cnt){
	if(numHouse == cnt){
		if(x == church.x || y == church.y) res++;
		return;
	}
	int i, j;
	for(i=0; i<4; i++){
		for(j=0; j<dir[i][y][x].size(); j++){
			if(!chk[dir[i][y][x][j].y][dir[i][y][x][j].x]){
				chk[dir[i][y][x][j].y][dir[i][y][x][j].x] = 1;
				fly(dir[i][y][x][j].x, dir[i][y][x][j].y, cnt+1);
				chk[dir[i][y][x][j].y][dir[i][y][x][j].x] = 0;
				break;
			}
		}
	}
}

int main(){
	scanf("%d%d", &m, &n);

	int i, j, k;
	for(i=1; i<=n; i++){
		for(j=1; j<=m; j++){
			scanf("%d", &map[i][j]);
			if(map[i][j] == 2) church.x = j, church.y = i;
			else if(map[i][j] == 1) numHouse++;
		}
	}

	pos tmp;
	for(i=1; i<=n; i++){
		tmp.y = i;
		for(j=1; j<=m; j++){
			if(map[i][j] == 1){
				tmp.x = j;
				for(k=j-1; k>=1; k--)
					if(map[i][k] > 0) dir[0][i][k].push_back(tmp);
			}
		}
		for(j=m; j>=1; j--){
			if(map[i][j] == 1){
				tmp.x = j;
				for(k=j+1; k<=m; k++)
					if(map[i][k] > 0) dir[1][i][k].push_back(tmp);
			}
		}
	}
	for(j=1; j<=m; j++){
		tmp.x = j;
		for(i=1; i<=n; i++){
			if(map[i][j] == 1){
				tmp.y = i;
				for(k=i-1; k>=1; k--)
					if(map[k][j] > 0) dir[2][k][j].push_back(tmp);
			}
		}
		for(i=n; i>=1; i--){
			if(map[i][j] == 1){
				tmp.y = i;
				for(k=i+1; k<=n; k++)
					if(map[k][j] > 0) dir[3][k][j].push_back(tmp);
			}
		}
	}

	fly(church.x, church.y, 0);

	printf("%d\n", res);

	return 0;
}

	
#include <stdio.h>    // Best solution for Good Pattern By Winner!!
												 // using mem cutting 2^21*2^21 -> 2*2^21
const int mod = 100000;
int N,M,C; char S[22][22];
int D[2][3][1<<21],f;

void sum(int& a, int b){a = (a + b) % mod;}

int main()
{
	int i,j,k,c;

	scanf ("%d %d",&N,&M); C = 1;
	for (i=0;i<N;i++){
		scanf ("%s",S[i]);
		for (j=0;j<M;j++){
			if (S[i][j] == '?') C = (C * 3) % mod;
		}
	}

	D[1][0][0] = 1;
	for (i=0;i<N;i++) for (j=0;j<M;j++){
		for (k=0;k<(1<<M);k++) D[f][0][k] = D[f][1][k] = D[f][2][k] = 0;
		for (k=0;k<(1<<M);k++){
			c = (D[!f][0][k] + D[!f][1][k] + D[!f][2][k]) % mod;

			if (S[i][j] == 'K' || S[i][j] == '?') sum(D[f][0][k>>1],c);
			if ((S[i][j] == 'I' || S[i][j] == '?') && (k & 1) == 0) sum(D[f][2][k>>1],c);
			if (j == 0){
				if (S[i][j] == 'O' || S[i][j] == '?') sum(D[f][1][k>>1],c);
			}
			else{
				if(S[i][j] == 'O' || S[i][j] == '?'){
					sum(D[f][1][k>>1],D[!f][1][k]+D[!f][2][k]);
					sum(D[f][1][(k>>1)+(1<<(M-2))],D[!f][0][k]);
				}
			}
		}

		f = !f;
	}

	c = 0;
	for (k=0;k<(1<<M);k++){
		c = (c + D[!f][0][k] + D[!f][1][k] + D[!f][2][k]) % mod;
	}
	printf ("%d",(C-c+mod)%mod);

	return 0;
}

	#include<stdio.h>						// This is Dynamic Programming (named Bitonic Tour) best solution!!
	#define max(a,b) (a>b?(a):(b))
	int d[220][110][110],n,m;
	int s[110][110];
	main()
	{
		int i,j,k;
		scanf("%d%d",&m,&n);
		for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%1d",&s[i][j]);
		for(i=1;i<=n;i++) for(j=1;j<=m;j++)	s[i][j]=s[i][j]==1?1:s[i][j]==0?0:-1;
		for(k=2,d[1][1][1]=s[1][1]+1;k<n+m;k++) for(i=1;i<=n;i++)
		{
			if(s[i][k-i+1]==-1) continue;
			for(j=i;j<=n;j++)
			{
				int score=0;
				if(i!=j) score = s[i][k-i+1]+s[j][k-j+1];
				else score = s[i][k-i+1];
				if(s[j][k-j+1]==-1) continue;
				d[k][i][j] = max(d[k-1][i-1][j],max(d[k-1][i][j-1],max(d[k-1][i][j],d[k-1][i-1][j-1])));
				d[k][i][j] = d[k][i][j]?d[k][i][j]+score:0;
			}
		}
		printf("%d\n",d[n+m-1][n][n]?d[n+m-1][n][n]-1:0);
	}