G: Computer Onesan / コンピュータおねえさん

ある日，おねえさんは，子供たちに組合せの数え方について教えてあげることになりました．

そこで，おねえさんは，次のような問題を解いてみることにしました．

図1に，N = 2, M = 2 の場合の全ての通り方を示します． 図1では，全部で12通りの通り方を示しており，その経路は赤い太線で表しています．

G_fig.png

図1: N = 2, M = 2 の場合の全ての通り方

この問題では， N と M が少し大きくなるだけで，組合せの数が爆発的に増加してしまい，手で数えるのがとても難しくなってしまいます． そこで，おねえさんは，自分の頭脳をロボットに移植し，25万年をかけて，10 x 10 の場合の組合せの数を数える計画を立てました．

「10 x 10 なんて計算するとおねえさん死んじゃう！やめて！」

止める子供たちをよそに，おねえさんは，計算を開始します． おねえさんは，そこまでしてでも，子供たちに組合せ爆発のすごさを教えてあげたいのです．

おねえさんの熱意に心打たれたプログラマーのあなたは，この問題を解くプログラムを書いてあげることにしました． といっても，いきなり 10 x 10 を計算するプログラムを作るのは難しいので，手始めに M が小さい場合のプログラムを書くことにしました．

Input

入力は，1行に， N と M が半角スペースで与えられます． N は長方形の縦の幅で，1 <= N <= 100を満たします． M は長方形の横の幅で，1 <= M <= 2を満たします．

Output

入力に対する通り方の数を1行に出力してください． ただし，答えが非常に大きくなる場合があるので，1,000,000で割った余りを出力してください．

Sample Input 1

1 1

Sample Output 1

2

Sample Input 2

1 2

Sample Output 2

4

Sample Input 3

2 1

Sample Output 3

4

Sample Input 4

2 2

Sample Output 4

12

Sample Input 5

3 2

Sample Output 5

38