B. Baom and Fibonacci
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As we know the Fibonacci sequence is:

$$$$$$ fib(n) = \begin{cases} 1 &n=1 \ or \ n=2 \\ fib(n-1) + fib(n-2) & n \gt 2 \end{cases} $$$$$$

Baom wonder the value of function:

$$$$$$ f(n)=\sum_{i=1}^n\sum_{j=1}^n\gcd(fib(i),fib(j)) \bmod 998244353 $$$$$$

Input

One line contains a sigle integer $$$n(1 \leq n \leq 10^{10})$$$.

Output

Print a single integer $$$f(n) \bmod 998244353$$$.

Example
Input
3
Output
10