시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 249 90 77 48.125%

문제

상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 

남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대로 번호가 1, 2, ..., h로 매겨져 있다. 서쪽에서 i번째 남북 방향 도로와 남쪽에서 j번째 동서 방향 도로가 만나는 교차로는 (i, j)이다.

상근이는 교차로 (1, 1)에 살고 있고, 교차로 (w, h)에 있는 회사에 차로 다니고 있다. 차는 도로로만 이동할 수 있다. 상근이는 회사에 최대한 빨리 가기 위해서, 동쪽 또는 북쪽으로만 이동할 수 있다. 또, 이 도시는 교통 사고를 줄이기 위해서 교차로를 돈 차량은 그 다음 교차로에서 다시 방향을 바꿀 수 없다. 즉, 교차로에서 방향을 바꾼 후, 1 블록만 이동한 후 다시 방향을 바꿀 수 없다.

상근이가 회사에 출근할 수 있는 경로의 수는 몇 가지 일까?

w와 h가 주어졌을 때, 가능한 출근 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 w와 h가 주어진다. (2 ≤ w, h ≤ 100)

출력

첫째 줄에 상근이가 출근할 수 있는 경로의 개수를 100000로 나눈 나머지를 출력한다.

예제 입력 1

3 4

예제 출력 1

5

힌트

W3sicHJvYmxlbV9pZCI6IjU1NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkOWNcdWFkZmMgXHVhY2JkXHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMGFjXHViMjk0IFx1YjNjNFx1YzJkY1x1YjI5NCBcdWIwYThcdWJkODEgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YjNjNFx1Yjg1Y1x1YWMwMCB3XHVhYzFjLCBcdWIzZDlcdWMxMWMgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YjNjNFx1Yjg1Y1x1YWMwMCBoXHVhYzFjIFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMGE4XHViZDgxIFx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjMTFjXHVjYWJkXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWFjMDAgMSwgMiwgLi4uLCB3XHViODVjIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHViM2Q5XHVjMTFjIFx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWIyOTQgXHViMGE4XHVjYWJkXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWFjMDAgMSwgMiwgLi4uLCBoXHViODVjIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzExY1x1Y2FiZFx1YzVkMFx1YzExYyBpXHViYzg4XHVjOWY4IFx1YjBhOFx1YmQ4MSBcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHVjNjQwIFx1YjBhOFx1Y2FiZFx1YzVkMFx1YzExYyBqXHViYzg4XHVjOWY4IFx1YjNkOVx1YzExYyBcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHVhYzAwIFx1YjljY1x1YjA5OFx1YjI5NCBcdWFkNTBcdWNjMjhcdWI4NWNcdWIyOTQgKGksIGopXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhZDUwXHVjYzI4XHViODVjICgxLCAxKVx1YzVkMCBcdWMwYjRcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWFkNTBcdWNjMjhcdWI4NWMgKHcsIGgpXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQ2OGNcdWMwYWNcdWM1ZDAgXHVjYzI4XHViODVjIFx1YjJlNFx1YjJjOFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Y2MyOFx1YjI5NCBcdWIzYzRcdWI4NWNcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ2OGNcdWMwYWNcdWM1ZDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmU2OFx1YjlhYyBcdWFjMDBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWIzZDlcdWNhYmQgXHViNjEwXHViMjk0IFx1YmQ4MVx1Y2FiZFx1YzczY1x1Yjg1Y1x1YjljYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWM3NzQgXHViM2M0XHVjMmRjXHViMjk0IFx1YWQ1MFx1ZDFiNSBcdWMwYWNcdWFjZTBcdWI5N2MgXHVjOTA0XHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFkNTBcdWNjMjhcdWI4NWNcdWI5N2MgXHViM2M4IFx1Y2MyOFx1YjdjOVx1Yzc0MCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YzVkMFx1YzExYyBcdWIyZTRcdWMyZGMgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWM5ODksIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YzVkMFx1YzExYyBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHVhZmJjIFx1ZDZjNCwgMSBcdWJlMTRcdWI4NWRcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTVjIFx1ZDZjNCBcdWIyZTRcdWMyZGMgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVkNjhjXHVjMGFjXHVjNWQwIFx1Y2Q5Y1x1YWRmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWIyOTQgXHViYTg3IFx1YWMwMFx1YzljMCBcdWM3N2NcdWFlNGM/PFwvcD5cclxuXHJcbjxwPlxyXG5cdHdcdWM2NDAgaFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDljXHVhZGZjIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIHdcdWM2NDAgaFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgdywgaCAmbGU7IDEwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWNkOWNcdWFkZmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIDEwMDAwMFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wYXRoLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDMzMnB4OyBoZWlnaHQ6IDI5M3B4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTU2OSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1OTAxYVx1NTJlNFx1N2Q0Y1x1OGRlZiIsImRlc2NyaXB0aW9uIjoiPHA+Sk9JXHUzMDU1XHUzMDkzXHUzMDRjXHU0ZjRmXHUzMDgwXHUzMGFiXHUzMGNhXHUzMGMwXHUzMDZlXHUzMDQyXHUzMDhiXHU5MGZkXHU1ZTAyXHUzMDZmXHVmZjBjXHU1MzU3XHU1MzE3XHU2NWI5XHU1NDExXHUzMDZiXHUzMDdlXHUzMDYzXHUzMDU5XHUzMDUwXHUzMDZiXHU0ZjM4XHUzMDczXHUzMDhiIHcgXHU2NzJjXHUzMDZlXHU5MDUzXHU4ZGVmXHUzMDY4XHVmZjBjXHU2NzcxXHU4OTdmXHU2NWI5XHU1NDExXHUzMDZiXHUzMDdlXHUzMDYzXHUzMDU5XHUzMDUwXHUzMDZiXHU0ZjM4XHUzMDczXHUzMDhiIGggXHU2NzJjXHUzMDZlXHU5MDUzXHU4ZGVmXHUzMDZiXHUzMDg4XHUzMDhhXHVmZjBjXHU3ODgxXHU3NmU0XHUzMDZlXHU3NmVlXHUzMDZlXHU1ZjYyXHUzMDZiXHU1MzNhXHU1MjA2XHUzMDUxXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTM1N1x1NTMxN1x1NjViOVx1NTQxMVx1MzA2ZSB3IFx1NjcyY1x1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2Ylx1MzA2Zlx1ZmYwY1x1ODk3Zlx1MzA0Ylx1MzA4OVx1OTgwNlx1MzA2YiAxLCAyLCAuLi4gLCB3IFx1MzA2ZVx1NzU2YVx1NTNmN1x1MzA0Y1x1NGVkOFx1MzA1MVx1MzA4OVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA3ZVx1MzA1Zlx1ZmYwY1x1Njc3MVx1ODk3Zlx1NjViOVx1NTQxMVx1MzA2ZSBoIFx1NjcyY1x1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2Ylx1MzA2Zlx1ZmYwY1x1NTM1N1x1MzA0Ylx1MzA4OVx1OTgwNlx1MzA2YiAxLCAyLCAuLi4gLCBoIFx1MzA2ZVx1NzU2YVx1NTNmN1x1MzA0Y1x1NGVkOFx1MzA1MVx1MzA4OVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1ODk3Zlx1MzA0Ylx1MzA4OSBpIFx1NzU2YVx1NzZlZVx1MzA2ZVx1NTM1N1x1NTMxN1x1NjViOVx1NTQxMVx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2OFx1ZmYwY1x1NTM1N1x1MzA0Ylx1MzA4OSBqIFx1NzU2YVx1NzZlZVx1MzA2ZVx1Njc3MVx1ODk3Zlx1NjViOVx1NTQxMVx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA0Y1x1NGVhNFx1MzA4Zlx1MzA4Ylx1NGVhNFx1NWRlZVx1NzBiOVx1MzA5MiAoaSwgaikgXHUzMDY3XHU4ODY4XHUzMDU5XHVmZjBlPFwvcD5cclxuXHJcbjxwPkpPSVx1MzA1NVx1MzA5M1x1MzA2Zlx1ZmYwY1x1NGVhNFx1NWRlZVx1NzBiOSAoMSwgMSkgXHUzMDZlXHU4ZmQxXHUzMDRmXHUzMDZiXHU0ZjRmXHUzMDkzXHUzMDY3XHUzMDRhXHUzMDhhXHVmZjBjXHU0ZWE0XHU1ZGVlXHU3MGI5ICh3LCBoKSBcdTMwNmVcdThmZDFcdTMwNGZcdTMwNmVcdTRmMWFcdTc5M2VcdTMwNmJcdThlY2FcdTMwNjdcdTkwMWFcdTMwNjNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdThlY2FcdTMwNmZcdTkwNTNcdThkZWZcdTMwNmJcdTZjYmZcdTMwNjNcdTMwNjZcdTMwNmVcdTMwN2ZcdTc5ZmJcdTUyZDVcdTMwNTlcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdWZmMGVKT0lcdTMwNTVcdTMwOTNcdTMwNmZcdWZmMGNcdTkwMWFcdTUyZTRcdTY2NDJcdTk1OTNcdTMwOTJcdTc3ZWRcdTMwNGZcdTMwNTlcdTMwOGJcdTMwNWZcdTMwODFcdWZmMGNcdTY3NzFcdTMwN2VcdTMwNWZcdTMwNmZcdTUzMTdcdTMwNmJcdTMwNmVcdTMwN2ZcdTU0MTFcdTMwNGJcdTMwNjNcdTMwNjZcdTc5ZmJcdTUyZDVcdTMwNTdcdTMwNjZcdTkwMWFcdTUyZTRcdTMwNTdcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwN2VcdTMwNWZcdWZmMGNcdTMwNTNcdTMwNmVcdTkwZmRcdTVlMDJcdTMwNjdcdTMwNmZcdWZmMGNcdTRlYTRcdTkwMWFcdTRlOGJcdTY1NDVcdTMwOTJcdTZlMWJcdTMwODlcdTMwNTlcdTMwNWZcdTMwODFcdTMwNmJcdWZmMGNcdTZiMjFcdTMwNmVcdTMwODhcdTMwNDZcdTMwNmFcdTRlYTRcdTkwMWFcdTg5OGZcdTUyNDdcdTMwNGNcdThhMmRcdTMwNTFcdTMwODlcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMWE8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdTRlYTRcdTVkZWVcdTcwYjlcdTMwOTJcdTY2ZjJcdTMwNGNcdTMwNjNcdTMwNWZcdThlY2FcdTMwNmZcdWZmMGNcdTMwNWRcdTMwNmVcdTc2ZjRcdTVmOGNcdTMwNmVcdTRlYTRcdTVkZWVcdTcwYjlcdTMwNjdcdTY2ZjJcdTMwNGNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmZcdTUxZmFcdTY3NjVcdTMwNmFcdTMwNDRcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdTMwNTlcdTMwNmFcdTMwOGZcdTMwNjFcdWZmMGNcdTRlYTRcdTVkZWVcdTcwYjlcdTMwNjdcdTY2ZjJcdTMwNGNcdTMwNjNcdTMwNWZcdTMwNDJcdTMwNjhcdTMwNmIxXHUzMGQ2XHUzMGVkXHUzMGMzXHUzMGFmXHUzMDYwXHUzMDUxXHU5MDMyXHUzMDkzXHUzMDY3XHU1MThkXHUzMDczXHU2NmYyXHUzMDRjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZmXHU4YTMxXHUzMDU1XHUzMDhjXHUzMDZhXHUzMDQ0XHVmZjBlXHUzMDUzXHUzMDZlXHUzMDY4XHUzMDRkXHVmZjBjSk9JXHUzMDU1XHUzMDkzXHUzMDZlXHU5MDFhXHU1MmU0XHU3ZDRjXHU4ZGVmXHUzMDZmXHU0ZjU1XHU5MDFhXHUzMDhhXHU4MDAzXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHUzMDYwXHUzMDhkXHUzMDQ2XHUzMDRiXHVmZjBlPFwvcD5cclxuXHJcbjxwPncgXHUzMDY4IGggXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHUzMDY4XHUzMDRkXHVmZjBjSk9JXHUzMDU1XHUzMDkzXHUzMDZlXHU5MDFhXHU1MmU0XHU3ZDRjXHU4ZGVmXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDkyIDEwMDAwMCBcdTMwNjdcdTUyNzJcdTMwNjNcdTMwNWZcdTRmNTlcdTMwOGFcdTMwOTJcdTUxZmFcdTUyOWJcdTMwNTlcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NTE2NVx1NTI5Ylx1MzBkNVx1MzBhMVx1MzBhNFx1MzBlYlx1MzA2ZjFcdTg4NGNcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGFcdWZmMGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjYyXHU1MDBiXHUzMDZlXHU2NTc0XHU2NTcwIHcsIGggKDIgXHUyMjY2IHcgXHUyMjY2IDEwMFx1ZmYwYyAyIFx1MjI2NiBoIFx1MjI2NiAxMDApIFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSB3IFx1MzA2Zlx1NTM1N1x1NTMxN1x1NjViOVx1NTQxMVx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2ZVx1NjcyY1x1NjU3MFx1ZmYwYyBoIFx1MzA2Zlx1Njc3MVx1ODk3Zlx1NjViOVx1NTQxMVx1MzA2ZVx1OTA1M1x1OGRlZlx1MzA2ZVx1NjcyY1x1NjU3MFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTUxZmFcdTUyOWJcdTMwNmZcdWZmMGNKT0lcdTMwNTVcdTMwOTNcdTMwNmVcdTkwMWFcdTUyZTRcdTdkNGNcdThkZWZcdTMwNmVcdTUwMGJcdTY1NzBcdTMwOTIgMTAwMDAwIFx1MzA2N1x1NTI3Mlx1MzA2M1x1MzA1Zlx1NGY1OVx1MzA4YVx1MzA2MFx1MzA1MVx1MzA5Mlx1NTQyYlx1MzA4MDFcdTg4NGNcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGF0aC5wbmdcIiBzdHlsZT1cImhlaWdodDoyOTNweDsgb3BhY2l0eTowLjk7IHdpZHRoOjMzMnB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM3N2NcdWJjZjhcdWM1YjQifV0=