Informatica Online Judge

  Commuting Road [0510 / 01FE]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 90   Total Tried : 109


The Champion of this Problem (C++) : gs17113 - ms / 393byte
My Best Submission (C++) : N/A

[]

Background

예찬이가 살고있는 한국의 어떤 도시는 완전한 계획도시라 모든 도로가 동서남북으로 쭉 뻗어있다.

이 도시는 남북으로 W개의 도로가 있고, 동서로 H개의 도로가 있어서 바둑판의 형태로 도로가 구성되어 있다.

- 남북 방향으로 뻗은 W개의 도로에는 서쪽으로부터 1, 2, ..., W의 번호가 붇어있다.
- 동서 방향으로 뻗은 H개의 도로에는 남쪽으로부터 1, 2, ..., H의 번호가 붙어있다.

서쪽으로부터 i번째와 남쪽으로 부터 j번째의 도로가 만나는 교차로을 (i, j)로 나타낸다.

예찬이는 이 도시의 교차로(1,1) 근처에 살고 있다. 교차로(W,H) 근처 위치에 예찬이가 다니는 학교가 있다. 예찬이는 집에서 학교까지 자전거로 통학을 하고 있다.

자전거는 도로위로만 다닐 수 있다. 예찬이는 통학시간을 최소화하기 위해서 동쪽과 북쪽으로만 이동한다. 그리고 이 도시는 교통사고를 줄이기 위해 다음과 같은 교통법규가 있다.

- 교차로에서 방향을 바꾼 차는 바로 다음 교차로에서는 방향을 바꿀 수 없다.

즉, 방향을 바꾼 교차로에서 최소 2블록 이상 진행해야 방향을 바꿀 수 있다.

예찬이는 교통법규를 지키면서 집에서 학교까지 가는 방법은 몇가지가 있을까? 이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 W와 H가 공백으로 구분되어 입력된다. (2≤W,H≤100)

Output

가능한 경우의 수를 100,000으로 나눈 나머지값을 출력한다.

* 테스트데이터의 60%는 W, H가 30미만의 값이다.

IO Example

입력
3 4

출력
5

*설명 : 다음과 같이 5가지가 된다.


Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]