当前没有测试数据。

G - 数列计数

得分：$600$ 分

问题描述

给定有 $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$ 得到的余数不同。

约束

• $2 \leq N \leq 10^7$
• $1 \leq M \leq 10^7$
• 输入中的所有数都是整数。

输入

从标准输入中按以下格式给出：

$N$ $M$

输出

打印结果。

3 4

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)$

276 10000000

909213205

请确保将结果取模 $998244353$。