003 - 脱出ゲーム

時間制限 1 秒 / メモリ制限 256 MB / 得点 1 / x 1 /


TLE
1sec
MLE
256MB
得点
1

問題

YTAくんは、人気ゲーム「YDK城からの脱出」で遊んでいます。
このゲームは、N階建てであるYDK城の1階に閉じ込められた主人公が、アクションをちょうどM回行ってN階にたどり着いたらクリアという内容のものです。
使用できるアクションは以下の3つです。

アクション Y : 一つ上の階に移動する。(ただし、N階では使用不可)
アクション D : 一つ下の階に移動する。(ただし、1階では使用不可)
アクション K : その階にとどまる。

YTAくんはこのゲームをクリアする方法が何通りあるか気になりました。
そこで、上のアクションをM回行って1階からN階まで到着する方法が何通りあるか、109+7で割った余りを求めてください。

入力

入力は以下の形式で与えられる。

N M

一行目に、YDK城の階数Nと行うアクションの数Mが空白区切りで与えられる。

出力

クリアする方法を109+7で割った余りを出力せよ。
ただし、クリアする方法がない場合は0を出力すること。

制約

1 ≦ N ≦ 3000
1 ≦ M ≦ 3000

入出力例

入力例1

2 3

出力例1

4

Y→D→Y
Y→K→K
K→Y→K
K→K→Y
の4パターンあります。

入力例2

10 5

出力例2

0

どのアクションを使っても10階にたどりつくことはできません。

入力例3

25 50

出力例3

582790102