Commute Route

Interview

Time limit1sMemory limit128 MB

Summary

Count monotone lattice paths from (1,1) to (w,h) that never turn at two consecutive intersections, modulo 100000.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Combinatorics, Implementation
Solved: No attempts yet

Problem

The city where Sang-geun lives has $w$ roads running north-south and $h$ roads running east-west.

The north-south roads are numbered $1, 2, \dots, w$ from west to east, and the east-west roads are numbered $1, 2, \dots, h$ from south to north. The intersection where the $i$ -th north-south road (counting from the west) meets the $j$ -th east-west road (counting from the south) is called $(i, j)$ .

Sang-geun lives at intersection $(1, 1)$ and drives to his company at intersection $(w, h)$ . A car may travel only along the roads. To reach the company as quickly as possible, Sang-geun moves only east or north.

To reduce traffic accidents, the city forbids a car that has just turned at an intersection from turning again at the very next intersection. In other words, after changing direction a car may not move just one block and immediately change direction again; it must go straight for at least two blocks before it may turn again.

Given $w$ and $h$ , write a program that counts the number of distinct routes Sang-geun can take to work.

Input

The first line contains two integers $w$ and $h$ . ( $2 \le w, h \le 100$ )

Output

Print the number of routes Sang-geun can take to work, modulo $100000$ .

Hint

After turning at an intersection, a car must go straight for at least two blocks before it can turn again; equivalently, it can never turn at two consecutive intersections. For example, when $w = 3$ and $h = 4$ there are exactly $5$ valid routes.

Examples2

Example 1
Input
```
3 4
```
Expected output
```
5
```
Example 2
Input
```
15 15
```
Expected output
```
43688
```