题目描述

灰灰现在有一个数列，其数值为：$1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193 \dots$，这一数列有如下的递推公式：$F(1) = 1, F(2) = 1, F(3) = 1, F(n+1) = F(n) + F(n - 1) + F(n - 2)(n \geq 3，n \in N^*）$。

现在，给与一个正整数 $n$，请你求出 $F(n)$ 的值，答案对 $998244353$ 取模。

输入输出格式

输入格式

一行一个整数 $n$。

输出格式

一行一个数，表示答案模 $998244353$ 的结果。

样例

输入

6

输出

9

数据范围

前五个测试点送分，$1 \leqslant n \leqslant 11$

除前五个测试点外：

• 对于 $30 \%$ 的数据，$1 \leqslant n \leqslant 100$；
• 对于 $70 \%$ 的数据，$1 \leqslant n \leqslant 10^6$；
• 对于 $100 \%$ 的数据，$1 \leq n \leq 10^9$。