题目描述

灰灰现在有一个数列，其数值为：\(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\)。