AT_abc276_g [ABC276G] Count Sequences

题目描述

求满足以下条件的项数为 $N$ 的整数序列 $A=(a_1,a_2,\ldots,a_N)$ 的个数，并将结果对 $998244353$ 取模。

• $0 \leq a_1 \leq a_2 \leq \ldots \leq a_N \leq M$。
• 对于每个 $i=1,2,\ldots,N-1$，$a_i$ 除以 $3$ 的余数与 $a_{i+1}$ 除以 $3$ 的余数不同。

输入格式

输入从标准输入中给出，格式如下：

$N$ $M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 4

输出 #1

8

输入输出样例 #2

输入 #2

276 10000000

输出 #2

909213205

说明/提示

限制条件

• $2 \leq N \leq 10^7$
• $1 \leq M \leq 10^7$
• 输入均为整数

样例解释 1

以下 $8$ 个序列满足条件：

• $(0,1,2)$
• $(0,1,3)$
• $(0,2,3)$
• $(0,2,4)$
• $(1,2,3)$
• $(1,2,4)$
• $(1,3,4)$
• $(2,3,4)$

样例解释 2

请将个数对 $998244353$ 取模后输出。

由 ChatGPT 4.1 翻译