矩阵快速幂签到

题号：NC261225
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\textbf{快速幂}$ ：快速幂就是快速算底数的 $n$ 次幂。其时间复杂度为 $O(log_2n)$ ，与朴素的 $O(n)$ 相比效率有了极大的提高。快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
例如：
$\begin{align*} & 3^{5} \\ & =3\times3\times3\times3\times3 \\ & = (3\times3)\times(3\times3)\times3 \\ & = (3\times3\times3\times3)\times3 \\ & = 3^4 \times 3^1 \\ & = 81 \times 3 \\ & =243 \end{align*}$
相对于一般的快速幂，矩阵快速幂仅仅是把他的底数和乘数换成了矩阵形式，而相应的乘法等运算也遵循矩阵的运算法则。对于矩阵的基本运算这里不再做赘述。
$\textbf{取模}$ ： $a \% p$ (或 $a \space mod \space p$ )，表示 $a$ 除以 $p$ 的余数。
现在给你一个递推公式：
$a(n) = \begin{cases}<br />1, & n=0 \\ 2, & n=1 \\<br />2 \times a(n-1)-a(n-2) , & n>1 \\<br />\end{cases}$
求该数列的第 $n$ 项。由于答案可能过大，你只需要输出答案对 $998244353$ 取模后的值。

输入描述:

一个正整数  () 。

输出描述:

一个整数，对应答案。

示例1

输入

复制

输出

复制

示例2

输入

复制

输出

复制

备注:

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