No.3399 One Two Three Two Three
タグ : / 解いたユーザー数 10
作問者 :
akakimidori
/ テスター :
noshi91
Problem Statement
You are given an integer $N$.
A variable $x$ is initialized as $x=1$.
From this point, while $x < N$, repeatedly choose one of the following $5$ operations and perform it.
- Update $x$ to $x+1$.
- Update $x$ to $x+2$.
- Update $x$ to $x+3$.
- Update $x$ to $2x$.
- Update $x$ to $3x$.
Input
$N$
- $1\leq N \leq 10^{18}$
Output
Output the number of operations modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
1
Output
1
In the initial state, $x = 1$ and the operations have already finished. Since no operation is performed, there is $1$ way.
Sample 2
Input
2
Output
2
After performing one operation, $x < 2$ no longer holds. The only ways to get $x=2$ with $1$ operation are choosing operation 1. or operation 4. There are $2$ ways, so output $2$.
Sample 3
Input
3
Output
4
Sample 4
Input
10
Output
401
Sample 5
Input
100
Output
888004452
Note that you must output the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。