Description

Original problem link.

Given $l, r, k$, compute:

where $f_0 = 0$, $f_1 = 1$, and $f_n = f_{n-1} + f_{n-2} \ (n \geq 2)$.
As a “kind-hearted” (not really) problem setter, you only need to take the answer modulo $998244353$.

Input Format

Input one line with three positive integers $l, r, k$.

Output Format

Output one line with one integer, representing the answer.

233 888 251

60539267

11451 45149 8100

728539702

114514 233333 101010

830578369

198245 285628 157293

121742791

Hint

Constraints.
For $30\%$ of the testdata, $1 \le k \le 1000$.
For $70\%$ of the testdata, $1 \le k \le 10^5$.
For $100\%$ of the testdata, $1 \le k \le 5 \times 10^5$, $1 \le l \le r \le 10^{18}$.

Please pay attention to constant-factor optimizations.

Since setting $l, r$ to an arbitrary-precision range is not very meaningful, it has been changed to 10^{18} here.

Translated by ChatGPT 5