题目描述

你正在玩 Felis。

整个叠键段可以抽象为 $n$ 组互不相同的 note，编号为 $1,2,\ldots,n$。初始时，COMBO 和分数均为 $0$。

每组 note 可以按以下方式处理：

1. 单独处理一组 note 时，可以选择“双指交互”或“单指纵连”，两种方式都会使分数增加 $1$；
2. 可以将连续的两组 note 一起处理。此时不再考虑这两组 note 各自的选择，而是选择：
   • 硬抗：分数不增加；
   • 拆分手法：分数增加 $2$，并使 COMBO 增加 $1$。

需要注意的是，第 $i$ 组 note 最多只能和第 $i-1$ 组与第 $i+1$ 组中的一组一起处理。也就是说，被一起处理的相邻 note 对之间不能重叠。

考虑所有合法的处理方案。你需要计算：

• 所有 COMBO 为偶数的方案中，分数的 $k$ 次方之和；
• 减去所有 COMBO 为奇数的方案中，分数的 $k$ 次方之和。

答案对 $998244353$ 取模。

输入格式

一行两个整数 $n,k$。

输出格式

输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例输入

3 2

样例输出

40

样例解释

用 A 表示双指交互，B 表示单指纵连；中括号表示相邻两组 note 一起处理；C 表示硬抗，D 表示拆分手法。

COMBO 为偶数的方案为：

AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB,
A[C], B[C], [C]A, [C]B

这些方案的分数平方之和为 $76$。

COMBO 为奇数的方案为：

A[D], B[D], [D]A, [D]B

这些方案的分数平方之和为 $36$。

因此答案为

数据范围

• 对于 $10\%$ 的数据，$1\le n\le 10^2$，$1\le k\le 10^2$；
• 对于 $30\%$ 的数据，$1\le n\le 10^9$，$1\le k\le 10^3$；
• 对于 $60\%$ 的数据，$1\le n\le 10^9$，$1\le k\le 10^5$；
• 对于 $100\%$ 的数据，$1\le n\le 10^9$，$1\le k\le 10^7$。