No.1073 Infinite Sugoroku
タグ : / 解いたユーザー数 193
作問者 :
Kiri8128
/ テスター :
nmnmnmnmnmnmnm
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もしくは右上の雲マークをクリックしてアカウントを作成してください。