問題一覧 > 通常問題

No.834 Random Walk Trip

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 49
作問者 : leaf_1415leaf_1415 / テスター : tempura_pptempura_pp
16 ProblemId : 2749 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-04-06 19:37:53

問題文

世界には$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$で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。