题目描述

用 $1 \times 2$ 和 $2 \times 1$ 两种地砖（每种地砖都无限量供应）填充 $m$ 行 $n$ 列的网格，要求不重叠且铺满。 设填充 $m$ 行 $n$ 列网格的方案数为 $f[n]$ 。 现在 $n$ 的具体值丟失了，只知道一个范围 $[l, r]$ ，请你求出 $\sum_{i=l}^r f(i) ， \bmod 998244353$ 。

输入格式

第一行为 2 个正整数 $l, r$ 。 第二行为 1 个正整数 $m$ 。

输出格式

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

2 2
2

2

123 345
3

164772881

12324 34512412
6

921818959

数据规模与约定

由于 $l, r$ 的数值可能很大，我们用 $l e n$ 表示 $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$

大样例

大样例下载