题目描述

斐波那契数列是一个满足如下要求的数列

$$\begin{cases} F_1 = 1 \\ F_2 = 1 \\ F_i = F_{i-1} + F_{i-2} \ (i > 2) \end{cases} $$

我们规定一个类似的数列满足

$$\begin{cases} G_1 = 2 \\ G_2 = 3 \\ G_i = G_{i-1} \times G_{i-2} \ (i > 2) \end{cases} $$

求该数列 $G$ 的前 $n$ 项的乘积对 $998244353$ 取模的结果。

输入格式

输入一行包含一个正整数 $n$。

输出格式

输出一行包含一个整数表示答案。

5

69984

提示

【评测用例规模与约定】

对于 70% 的评测用例，$n \leq 10^6$；

对于所有评测用例，$1 \leq n \leq 10^{18}$。