题目描述

原题链接

给定 $l,r,k$，求：

其中 $f_0= 0$，$f_1 = 1$，$f_n = f_{n-1}+f_{n-2} \ (n \geq 2)$。
作为良心（迫真）出题人，你只需要将答案对 $998244353$ 取模。

输入格式

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

输出格式

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

233 888 251

60539267

11451 45149 8100

728539702

114514 233333 101010

830578369

198245 285628 157293

121742791

提示

【数据范围】
对于 $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}$ 了。