P1034 - Count Sequences

Memory Limit：1024 MB Time Limit：4.000 S

Judge Style：Text Compare Creator：

Submit：20 Solved：7

Submit Submit Record Statistics ShowOff!

Find the number of sequences of integers with $lns="http://www.w3.org/1998/Math/MathML"> �$ terms, $lns="http://www.w3.org/1998/Math/MathML"> � = (�_{1}, �_{2}, \dots, �_{�})$ , that satisfy the following conditions, modulo $lns="http://www.w3.org/1998/Math/MathML"> 998244353$ .

$lns="http://www.w3.org/1998/Math/MathML"> 0 \leq �_{1} \leq �_{2} \leq \dots \leq �_{�} \leq �$ .
For each $lns="http://www.w3.org/1998/Math/MathML"> � = 1, 2, \dots, � - 1$ , the remainder when $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ is divided by $lns="http://www.w3.org/1998/Math/MathML"> 3$ is different from the remainder when $lns="http://www.w3.org/1998/Math/MathML"> �_{� + 1}$ is divided by $lns="http://www.w3.org/1998/Math/MathML"> 3$

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

 $N$   $lns="http://www.w3.org/1998/Math/MathML"> �$

$2 \leq N \leq 1 0^{7}$
$lns="http://www.w3.org/1998/Math/MathML"> 1 \leq � \leq 1 0^{7}$
All values in the input are integers.


	 $lns="http://www.w3.org/1998/Math/MathML"> �$ 
	

		 $lns="http://www.w3.org/1998/Math/MathML">$

Print the answer.

3 4

Here are the eight sequences that satisfy the conditions.

$lns="http://www.w3.org/1998/Math/MathML"> (0, 1, 2)$
$lns="http://www.w3.org/1998/Math/MathML"> (0, 1, 3)$
$lns="http://www.w3.org/1998/Math/MathML"> (0, 2, 3)$
$lns="http://www.w3.org/1998/Math/MathML"> (0, 2, 4)$
$lns="http://www.w3.org/1998/Math/MathML"> (1, 2, 3)$
$lns="http://www.w3.org/1998/Math/MathML"> (1, 2, 4)$
$lns="http://www.w3.org/1998/Math/MathML"> (1, 3, 4)$
$lns="http://www.w3.org/1998/Math/MathML"> (2, 3, 4)$

Atcoder

Submit Submit Record Statistics ShowOff!

1034: Count Sequences

Description

Input

Output

Sample Input Copy

Sample Output Copy

HINT

Source/Category