P6358 鬼故事 加强版

[原题链接](https://www.luogu.com.cn/problem/P5126) 给定 $l,r,k$，求： $$\sum_{i=l}^r \prod_{j=i}^{i+k-1}f_j$$ 其中 $f_0= 0$，$f_1 = 1$，$f_n = f_{n-1}+f_{n-2} \ (n \geq 2)$。 作为良心（迫真）出题人，你只需要将答案对 $998244353$ 取模。

输入一行三个正整数 $l,r,k$。

输出一行一个整数，表示答案。

【数据范围】 对于 $30\%$ 的数据，$1\le k \le 1000$； 对于 $70\%$ 的数据，$1\le k \le 10^5$； 对于 $100\%$ 的数据，$1\le k \le 5 \times 10^5$，$1\le l \le r \le 10^{18}$。 **请注意常数优化。** 由于 $l,r$ 开到高精度范围也没什么意义，因此这里就改为 $10^{18}$ 了。