No.834 Random Walk Trip

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 23
作問者 : leaf_1415leaf_1415 / テスター : tempura_pptempura_pp
7 ProblemId : 2749 / 出題時の順位表

問題文

世界には$N$個の国があり、それぞれ国$1,$ 国$2,$ $\ldots,$ 国$N$と呼ばれています。
国$1$に住んでいるA君は、$M$日間かけて世界を旅行する計画しています。
ただ旅行するだけではつまらないと感じたA君は、旅の過程をコインで決めることにしました。

旅行の日程は$1$日目, $2$日目, $\ldots,$ $M$日目からなり、A君は$1$日目の始めには国$1$にいます。
$i$日目の始めにA君がいる国を国$x$とすると、A君が$i$日目にとる行動は以下のようになります。
(1) コインを投げて表と裏のどちらが出たかを観測します。
(2) 表が出た場合、$x > 1$ならばA君は国$x-1$に移動します。$x = 1$ならばA君は何もしません。
裏が出た場合、$x < N$ならばA君は国$x+1$に移動します。$x = N$ならばA君は何もしません。
(3) 上記(2)の後にA君がいる国を国$y$とします。A君は旅行記の$i$ページ目に$y$と書き加えます。

$M$日目が終わったあとに、旅行記の$i$ページ目に記されている整数を$a_i$とするとき、
数列$a_1, a_2, \ldots, a_M$としてありうるものであって、$a_M = 1$を満たすものの総数を求めてください。
ただし、答えは非常に大きくなることがあるので、答えを$10^9+7$で割った余りを出力してください。

入力

$N\ M$

入力は以下の制約を満たします。
$1 \leq N \leq 10^6$
$1 \leq M \leq 10^6$
$N,\ M$はどちらも整数

出力

条件を満たす数列の個数を$10^9+7$で割ったあまりを1行に出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2 3
出力
4

投げたコインの表裏が、1日目から順に(裏、裏、表)だったとすると、
1日目に国1から国2に移動し、2日目には国2にとどまり、3日目には国2から国1に帰るので、数列$\{a_i\}$は$2, 2, 1$となります。
同様に、
(裏、表、表)のとき数列$\{a_i\}$は$2, 1, 1$
(表、表、表)のとき数列$\{a_i\}$は$1, 1, 1$
(表、裏、表)のとき数列$\{a_i\}$は$1, 2, 1$
となり、問題の条件を満たす数列はこれですべてです。
よって、答えは$4$です。

サンプル2
入力
1 2
出力
1

数列$\{a_i\}$としてありうるものは$1, 1$のみです。

サンプル3
入力
16 21
出力
352716

サンプル4
入力
1000000 1000000
出力
996692777

答えを$10^9+7$で割った余りを出力してください。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。