p00470 Commute routes_9806
problem

A city in Canada where JOI lives is divided into a grid pattern by w roads that extend straight in the north-south direction and h roads that extend straight in the east-west direction.

The w roads in the north-south direction are numbered 1, 2, ..., w in order from the west. In addition, h roads in the east-west direction are numbered 1, 2, ..., h in order from the south. The intersection of the i-th north-south road from the west and the j-th east-west road from the south is represented by (i, j).

JOI lives near the intersection (1, 1) and drives to a company near the intersection (w, h). Cars can only move along the road. JOI travels only to the east or north to shorten his commute time. The city also has the following traffic rules to reduce traffic accidents:

* A car that turns at an intersection cannot turn at the intersection immediately after that.



That is, it is not permissible to go one block after turning at an intersection and turn again. At this time, how many possible commuting routes for Mr. JOI?

Given w and h, create a program that outputs the remainder of JOI's number of commuting routes divided by 100000.



input

The input consists of multiple datasets. Each dataset consists of one line, and two integers w, h (2 ≤ w ≤ 100, 2 ≤ h ≤ 100) are written, separated by a blank. w represents the number of roads in the north-south direction, and h represents the number of roads in the east-west direction.

When both w and h are 0, it indicates the end of input. The number of data sets does not exceed 5.

output

For each data set, the remainder of JOI's number of commuting routes divided by 100000 is output on one line.

Example

Input

3 4
15 15
0 0


Output

5
43688
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#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>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))

using namespace std;

static const double EPS = 1e-9;
typedef long long ll;
typedef pair<int, int> paii;

int dp[2][1000][1000];//0...head east 1...head north

int solve(int w, int h)
{
	CLR(dp);
	
	FOR(k, 0, h+w+1)
	{
		dp[0][k][1] = 1;
		dp[1][k][1] = 1;
		dp[0][1][k] = 1;
		dp[1][1][k] = 1;
	}

	FOR(j, 2, h+1)
		FOR(i, 2, w+1)
		{
			dp[0][j][i] = (dp[0][j][i-1] + dp[1][j-2][i])%100000;
			dp[1][j][i] = (dp[1][j-1][i] + dp[0][j][i-2])%100000;
		}
		
	return (dp[0][h][w-1] + dp[1][h-1][w])%100000;
}

int main()
{
	int w, h;
	
	while(cin >> w >> h, (w||h))
	{
		cout << solve(w, h) << endl;
	}

	return 0;
}
3 4
15 15
0 0 3 4
15 20
0 0 3 4
15 24
0 0 3 4
15 34
0 0 4 4
15 34
0 0 3 4
15 16
0 0 3 5
15 34
0 0 4 4
12 34
0 0 1 4
15 16
0 0 2 4
12 34
0 0 2 1
12 34
0 0 4 2
22 34
0 0 4 3
22 34
0 0 4 3
13 34
0 0 6 3
13 34
0 0 6 3
13 25
0 0 4 4
15 33
0 0 3 4
26 24
0 0 3 5
15 60
0 0 4 4
12 40
0 0 1 4
7 16
0 0 4 2
12 43
0 0 3 2
12 18
0 0 4 2
18 34
0 0 4 5
13 34
0 0 6 3
13 65
0 0 6 3
13 38
0 0 8 4
15 33
0 0 4 7
12 40
0 0 4 2
12 63
0 0 4 4
18 34
0 0 6 2
13 65
0 0 6 5
13 38
0 0 6 7
12 40
0 0 1 6
7 31
0 0 4 3
18 34
0 0 2 6
7 31
0 0 5 4
15 15
0 0 3 3
15 24
0 0 3 4
15 39
0 0 4 4
12 68
0 0 3 7
15 16
0 0 4 7
12 34
0 0 2 4
9 34
0 0 4 2
12 65
0 0 7 3
22 34
0 0 6 3
22 34
0 0 6 3
17 25
0 0 8 4
15 22
0 0 3 4
14 24
0 0 3 5
15 68
0 0 4 4
8 40
0 0 3 2
24 18
0 0 4 2
7 34
0 0 7 5
13 34
0 0 1 3
13 65
0 0 6 3
13 70
0 0 8 4
15 21
0 0 4 2
24 63
0 0 7 4
18 34
0 0 6 2
7 65
0 0 6 2
12 40
0 0 4 3
18 25
0 0 2 7
7 32
0 0 3 6
15 15
0 0 3 4
15 61
0 0 3 7
18 16
0 0 7 3
22 43
0 0 6 3
23 25
0 0 3 2
14 24
0 0 1 5
8 34
0 0 4 1
12 18
0 0 3 2
24 3
0 0 1 2
18 34
0 0 1 3
7 65
0 0 6 4
13 70
0 0 8 4
21 21
0 0 1 8
8 16
0 0 7 4
18 33
0 0 4 4
18 25
0 0 2 7
10 32
0 0 3 7
34 16
0 0 8 2
6 65
0 0 3 2
22 24
0 0 1 2
18 24
0 0 1 3
12 65
0 0 8 4
13 70
0 0 8 4
21 40
0 0 7 4
8 33
0 0 8 2
6 95
0 0 3 2
22 17
0 0 10 4
13 70
0 0 3 2
36 17
0 0 10 4
13 80
0 0 1 7
6 65
0 0 3 4
36 17
0 0 1 7
9 65
0 0 3 5
36 17
0 0 3 4
17 16
0 0 3 5
20 34
0 0 4 4
12 60
0 0
5
43688 5
58046
 5
8663
 5
73960
 8
73960
 5
25033
 6
73960
 8
55628
 1
25033
 2
55628
 1
55628
 2
22108
 5
22108
 5
61707
 7
61707
 7
74473
 8
41241
 5
59054
 6
1260
 8
43422
 1
1102
 2
88219
 2
82484
 2
46250
 11
61707
 7
96871
 7
66726
 20
41241
 17
43422
 2
87132
 8
46250
 2
96871
 26
66726
 62
43422
 1
6912
 5
46250
 2
6912
 11
43688
 4
8663
 5
69456
 8
53954
 8
25033
 17
55628
 2
96567
 2
57382
 8
22108
 7
22108
 7
46051
 20
41347
 5
7326
 6
75186
 8
47890
 2
54776
 2
8938
 35
61707
 1
96871
 7
55422
 20
81764
 2
38007
 17
46250
 2
55345
 2
43422
 5
69828
 2
7550
 7
43688
 5
20122
 8
72406
 8
79250
 7
17029
 2
7326
 1
28842
 1
82484
 2
25
 1
46250
 1
55345
 14
55422
 20
74978
 1
2586
 17
79484
 8
69828
 2
26190
 8
42934
 2
8066
 2
97692
 1
54776
 1
57382
 20
55422
 20
84164
 17
26267
 2
17486
 2
95733
 26
55422
 2
46219
 26
77629
 1
8066
 5
46219
 1
75330
 6
46219
 5
70273
 6
14046
 8
89490
