Contest Duration: - (local time) (100 minutes) Back to Home
G - Count Sequences /

Time Limit: 4 sec / Memory Limit: 1024 MB

### 問題文

• 0 \leq a_1 \leq a_2 \leq \ldots \leq a_N \leq M
• i=1,2,\ldots,N-1 それぞれについて、「a_i3 で割った余り」と「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

### 出力例 2

909213205

Score : 600 points

### Problem Statement

Find the number of sequences of integers with N terms, A=(a_1,a_2,\ldots,a_N), that satisfy the following conditions, modulo 998244353.

• 0 \leq a_1 \leq a_2 \leq \ldots \leq a_N \leq M.
• For each i=1,2,\ldots,N-1, the remainder when a_i is divided by 3 is different from the remainder when a_{i+1} is divided by 3.

### Constraints

• 2 \leq N \leq 10^7
• 1 \leq M \leq 10^7
• All values in the input are integers.

### Input

The input is given from Standard Input in the following format:

N M

3 4

### Sample Output 1

8

Here are the eight sequences that satisfy the conditions.

• (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

### Sample Output 2

909213205

Be sure to find the count modulo 998244353.