ABABABA2026

Problem Description

In the alphabet, there are only two letters: A and B.

We consider strings of length $n$ consisting only of these letters.

A string is called correct if all the following conditions are met:

• the first and last letters are A;
• there are no two As in a row (the substring AA is forbidden);
• there are no three Bs in a row (the substring BBB is forbidden).

For example, the strings ABBA, ABABABA, ABBABABBA are correct, while the strings ABBAB, ABAABA, ABABBBA are not.

We need to find the number of correct strings of length $n$.

Input

The first line contains one integer $n$ $(4 \le n \le 10^6)$ — the length of the string.

Output

Output the number of correct strings of length $n$ modulo $998244353$.

Scoring System

4

1

6

2