問題一覧 > 通常問題

No.834 Random Walk Trip

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

問題文

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

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

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

入力

N M

入力は以下の制約を満たします。
1N106
1M106
N, Mはどちらも整数

出力

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

サンプル

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

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

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

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

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

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

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

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