{"raw_statement":[{"iden":"problem statement","content":"You have an integer $1$ and a die that shows integers between $1$ and $6$ (inclusive) with equal probability.  \nYou repeat the following operation while your integer is strictly less than $N$:\n\n*   Cast a die. If it shows $x$, multiply your integer by $x$.\n\nFind the probability, modulo $998244353$, that your integer ends up being $N$.\nHow to find a probability modulo $998244353$? We can prove that the sought probability is always rational. Additionally, under the constraints of this problem, when that value is represented as $\\frac{P}{Q}$ with two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R \\times Q \\equiv P\\pmod{998244353}$ and $0 \\leq R \\lt 998244353$. Find this $R$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^{18}$\n*   $N$ is an integer."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$"},{"iden":"sample input 1","content":"6"},{"iden":"sample output 1","content":"239578645\n\nOne of the possible procedures is as follows.\n\n*   Initially, your integer is $1$.\n*   You cast a die, and it shows $2$. Your integer becomes $1 \\times 2 = 2$.\n*   You cast a die, and it shows $4$. Your integer becomes $2 \\times 4 = 8$.\n*   Now your integer is not less than $6$, so you terminate the procedure.\n\nYour integer ends up being $8$, which is not equal to $N = 6$.\nThe probability that your integer ends up being $6$ is $\\frac{7}{25}$. Since $239578645 \\times 25 \\equiv 7 \\pmod{998244353}$, print $239578645$."},{"iden":"sample input 2","content":"7"},{"iden":"sample output 2","content":"0\n\nNo matter what the die shows, your integer never ends up being $7$."},{"iden":"sample input 3","content":"300"},{"iden":"sample output 3","content":"183676961"},{"iden":"sample input 4","content":"979552051200000000"},{"iden":"sample output 4","content":"812376310"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}