CF2041H.Sheet Music

图片由 ChatGPT 4o 生成。

Alice 喜欢唱歌。作为一名唱歌爱好者，Alice 听过无数首歌曲，并多次尝试演唱它们。然而，偶尔有些歌曲会让 Alice 感到无聊。经过一番研究，Alice 认为这是因为尽管她选择的歌曲都不相同，但由于她本能的偏好，这些歌曲在音乐上都非常相似。

为了彻底分析这一点，Alice 决定研究这些歌曲的乐谱。为方便起见，Alice 将一首长度为 $n$ 的歌曲表示为一个整数序列 $a_1, a_2, \ldots, a_n$，其中 $a_i$ 表示第 $i$ 个音符的音高。然后她定义了歌曲之间的“音乐等价”关系。两首长度为 $n$ 的歌曲 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$ 被认为在音乐上等价，当且仅当对于所有 $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}$。

例如，$1, 2, 3, 3, 2$ 和 $5, 9, 13, 13, 1$ 在音乐上等价，而 $1, 2, 3, 2, 1$ 和 $1, 2, 2, 2, 1$ 则不等价。经过长期练习，Alice 能够演唱音高范围在 $[1, k]$ 内的任意音符。她想知道，在将音乐等价的歌曲视为同一首的情况下，长度为 $n$、音高在她的范围内的不同歌曲有多少首。你能帮她计算这个数量吗？

由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

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

• $1\leq n\leq 10^6$
• $1\leq k \leq 10^9$

输出不同歌曲的数量，对 $998244353$ 取模。

由 ChatGPT 4.1 翻译