P12847 [蓝桥杯 2025 国 A] 斐波那契数列

斐波那契数列是一个满足如下要求的数列 $$\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$。

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

**【评测用例规模与约定】** 对于 70% 的评测用例，$n \leq 10^6$； 对于所有评测用例，$1 \leq n \leq 10^{18}$。