Score : 800 points
Given is a positive even number N.
Find the number of strings s of length N consisting of A
, B
, and C
that satisfy the following condition:
AB
or BA
is not allowed.For example, ABBC
satisfies the condition for N=4, because we can convert it as follows: ABBC
→ (erase BB
) → AC
→ (erase AC
) → (empty)
.
The answer can be enormous, so compute the count modulo 998244353.
Input is given from Standard Input in the following format:
N
Print the number of strings that satisfy the conditions, modulo 998244353.
2
7
Except AB
and BA
, all possible strings satisfy the conditions.
10
50007
1000000
210055358