斐波那契数列
题号：NC307952
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

\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。

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

输出描述:

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

输入

复制 
5

输出

复制 
69984