어떤 달걀회사에서 세로로 N칸, 가로로 M칸인 아래와 같은 상자가 있다.

다음은 N=4, M=3인 상자의 모양이고 O는 달걀이다.

이 상자에 달걀을 담으려고 한다. 달걀을 배치하는 조건은 다음과 같다.

상자의 가로줄에는 한 개의 달걀을 배치하거나, 한 개의 달걀도 배치하지 않을 수 있다.

2. 다음 예제와 같이 한 가로줄에 밑줄친 달걀처럼 두 개 이상을 배치할 수 없다.

3. 또한, 다음 예제와 같이 달걀이 세로로 붙어있게 배치할 수 없다.

첫째 줄에 상자의 세로크기 N(1≤N≤100,000)과 가로크기 M(1≤M≤100)이 공백을 사이에 두고 두 자연수로 주어진다.

첫째 줄에 조건을 지키면서 달걀을 배치하는 모든 경우의 수를 10000으로 나눈 나머지를 출력한다.