問題一覧 > 通常問題

No.1073 無限すごろく

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 186
作問者 : Kiri8128Kiri8128 / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
15 ProblemId : 4336 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-06-22 01:31:55

問題文

高橋くんは無限すごろくをします。無限すごろくでは、非負整数の名前が付いたマスが 0 から順に無限に並んでいます。高橋くんは最初 0 のマスにいて、サイコロを振り出た目の数のマスだけ進むのを無限に繰り返します。サイコロは 1 から 6 の目があり、それぞれちょうど 16 の確率で出ます。
非負整数 N が与えられるので、高橋くんが N のマスに止まる確率を計算し mod 109+7 で出力してください。

入力

N

1N1018
N は整数

出力

高橋くんが N のマスに止まる確率を mod 109+7 で出力してください。

サンプル

サンプル1
入力
1
出力
166666668

1 のマスに止まるには 1 回目に 1 の目を出す必要があります。この確率は 16 なので、これを mod 109+7 で表した 166666668 を出力します。

サンプル2
入力
2
出力
194444446

2 のマスに止まるには 1 回目に 2 の目を出すか、最初の 2 回でどちらも 1 の目を出す必要があります。この確率は 736 なので、これを mod 109+7 で表した 194444446 を出力します。

サンプル3
入力
31415
出力
624072331

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