409210: GYM103462 B Baom and Fibonacci
Memory Limit：256 MB
Time Limit：5 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
B. Baom and Fibonaccitime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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 > 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 $$$$$$
InputOne line contains a sigle integer $$$n(1 \leq n \leq 10^{10})$$$.
OutputPrint a single integer $$$f(n) \bmod 998244353$$$.
ExampleInput3Output
10