由 ChatGPT 4o 生成的图像。
爱丽丝喜欢唱歌。作为一名歌唱爱好者,Alice听过无数的歌曲,也多次尝试演唱。然而,偶尔有些歌曲会让爱丽丝感到无聊。经过一番研究,Alice 认为这是因为尽管她选择的歌曲各不相同,但由于她本能的偏好,它们在音乐上都是相似的。
为了彻底分析这一点,爱丽丝决定研究歌曲的乐谱。为了方便起见,Alice 将一首长度为 $$$n$$$ 的歌曲表示为整数序列 $$$a_1, a_2, \ldots, a_n$$$,其中 $$$a_i$$$ 是第 $$$i$$$ 个音符的音高。然后她定义了歌曲之间的音乐等同性。如果对于所有 $$$1\leq i<n$$$,$$$a_i、a_{i+1}$$$ 和 $$$b_{i}、b_{i+1}$$$ 都具有相同的音高关系。更具体地说,$$$a_i、a_{i+1}$$$ 和 $$$b_i、b_{i+1}$$$ 具有相同的音高关系,如果
- $$$a_i < a_{i + 1}$$$ 和 $$$b_i < b_{i + 1}$$$,
- $$$a_i = a_{i + 1}$$$ 和 $$$b_i = b_{i + 1}$$$,或
- $$$a_i > a_{i + 1}$$$ 和 $$$b_i > b_{i + 1}$$$。
经过长期坚持练习,Alice 能够唱出 $$$[1, k]$$$ 范围内的任何音符。如果我们将音乐上等效的歌曲视为同一首歌曲,她想知道在她的范围内有多少种长度为 $$$n$$$ 的不同歌曲。你能帮她算一下这个数字吗?
由于答案可能很大,请打印对 $$$998244353$$$ 取模的答案。
输入
唯一一行包含两个整数$$$n,k$$$。
- $$$1\leq n\leq 10^6$$$
- $$$1\leq k \leq 10^9$$$
输出
输出不同歌曲的数量对 $$$998244353$$$ 取模。
示例
输入 #1
3 2
输出 #1
7
输入 #2
5 3
输出 #2
67