問題一覧 > 通常問題

No.1073 Infinite Sugoroku

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 193
作問者 : Kiri8128 / テスター : nmnmnmnmnmnmnm
お気に入りにしたユーザー ProblemId : 4336 / 自分の提出
問題文最終更新日: 2020-06-22 01:31:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 251 (順位表) の他の問題:

Problem Statement

Takahashi plays Infinite Sugoroku. In Infinite Sugoroku, squares named with non-negative integers are lined up infinitely in order, starting from $0$. Takahashi starts on square $0$ and endlessly repeats the following: roll a die and advance by the number of squares shown on the die. The die has faces from $1$ to $6$, each of which appears with probability exactly $\displaystyle\frac{1}{6}$.
Given a non-negative integer $N$, compute the probability that Takahashi stops on square $N$ and output it ${\rm mod}\ 10^9+7$.

Input

$N$

$1\le N \le 10^{18}$
$N$ is an integer.

Output

Output the probability that Takahashi stops on square $N$, ${\rm mod}\ 10^9+7$.

Sample

Sample 1
Input
1
Output
166666668

To stop on square $1$, roll number $1$ must show a $1$. This probability is $\displaystyle\frac{1}{6}$, so output $166666668$, which represents it ${\rm mod}\ 10^9+7$.

Sample 2
Input
2
Output
194444446

To stop on square $2$, either roll number $1$ must show a $2$, or the first $2$ rolls must both show a $1$. This probability is $\displaystyle\frac{7}{36}$, so output $194444446$, which represents it ${\rm mod}\ 10^9+7$.

Sample 3
Input
31415
Output
624072331

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