P6358 Ghost Story (Enhanced Version).

[Original problem link](https://www.luogu.com.cn/problem/P5126). Given $l, r, k$, compute: $$\sum_{i=l}^r \prod_{j=i}^{i+k-1} f_j$$ 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 one line with three positive integers $l, r, k$.

Output one line with one integer, representing the answer.

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