Background

Special for beginners, ^_^

Description

$\textbf{快速幂}$：快速幂就是快速算底数的 $n$ 次幂。其时间复杂度为 $O(log_2n)$， 与朴素的 $O(n)$ 相比效率有了极大的提高。快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
例如(暗色模式看不清)：

相对于一般的快速幂，矩阵快速幂仅仅是把他的底数和乘数换成了矩阵形式，而相应的乘法等运算也遵循矩阵的运算法则。对于矩阵的基本运算这里不再做赘述。
$\textbf{取模}$：$a \% p$ (或 $a \space mod \space p$)，表示 $a$ 除以 $p$ 的余数。

现在给你一个递推公式：

求该数列的第 $n$ 项。由于答案可能过大，你只需要输出答案对 $998244353$ 取模后的值。

Format

Input

一个正整数 $n$ ($1 \leq n \leq 998244351$) 。

Output

一个整数，对应答案。

Samples

1

2

2

3

如果没有解题思路，可以算一下前几项看看。

Limitation

1s, 1024KiB for each test case.