← 返回题目列表

Codeforces · 2041/H

H. 乐谱

中文机器翻译题面 查看原题

由 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