問題一覧 > 通常問題

No.1073 無限すごろく

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

問題文

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

入力

$N$

$1\le N \le 10^{18}$
$N$ は整数

出力

高橋くんが $N$ のマスに止まる確率を ${\rm mod}\ 10^9+7$ で出力してください。

サンプル

サンプル1
入力
1
出力
166666668

$1$ のマスに止まるには $1$ 回目に $1$ の目を出す必要があります。この確率は $\displaystyle\frac{1}{6}$ なので、これを ${\rm mod}\ 10^9+7$ で表した $166666668$ を出力します。

サンプル2
入力
2
出力
194444446

$2$ のマスに止まるには $1$ 回目に $2$ の目を出すか、最初の $2$ 回でどちらも $1$ の目を出す必要があります。この確率は $\displaystyle\frac{7}{36}$ なので、これを ${\rm mod}\ 10^9+7$ で表した $194444446$ を出力します。

サンプル3
入力
31415
出力
624072331

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