城堡考古

题目信息

时间限制: 1s

空间限制: 256M

输入文件: decoration.in

输出文件: decoration.out

题目描述

考古学家发现了一座城堡，城堡的地板是由一种特质地砖铺成的。这些地砖有两种规格：$1\times2$ 和 $2\times1$。城堡的地板被分成了 $m$ 行 $n$ 列的网格，每个网格都需要被地砖覆盖，而且地砖不能重叠，必须铺满整个地板。

城堡的守护者是一位聪明的巫师，他掌握了一种神秘的魔法，可以计算出不同方式铺设地板的数量。他把这个问题定义为一个数学问题，设填充 $m$ 行 $n$ 列网格的方式数为 $f[n]$。

然而，城堡的历史文献中，关于 $n$ 的确切值已经失传，唯一留下的线索是一个范围 $[l, r]$。现在，你作为一位数学家，被派遣来解开这个古老的魔法之谜。

你的任务是计算出在给定范围 $[l, r]$ 内，所有可能的 $f[i]$ 的值之和，并模 $998244353$。即求 $\sum_{i=l}^{r} f[i]\mod 998244353$

输入格式

第一行为2个正整数 $l, r$

第二行为1个正整数 $m$

输出格式

输出答案对 $998244353$ 取模的结果

样例

样例输入1

2 2
2

样例输出1

2

样例输入2

123 345
3

样例输出2

164772881

样例输入3

12324 34512412
6

样例输出3

921818959

样例输入4

12324 34512412
6

样例输出4

921818959

数据范围与提示

由于 $l, r$ 的数值可能很大，用 $len$ 表示 $r$ 的位数

• 对于100%的数据，$1\leq m\leq 6, 1\leq l\leq r$
• 对于测试点1-3，$r\leq 4$
• 对于测试点4-6，$r\leq 60000$
• 对于测试点7-10，$r\leq 10^9$
• 对于测试点11-13，$len\leq 100$
• 对于测试点14-16，$len\leq 3000, l=r$
• 对于测试点17-20，$len\leq 3000$