#9169. 猪分身

猪学会了分身术，他正在数轴上练习这一术法。

初始时（第 $0$ 秒），猪（相当于 $1$ 个猪分身）位于原点（$x=0$）处。

$1$ 个第 $t$ 秒位于 $x=i$ 处的猪分身会在第 $t$ 秒结束后、第 $t+1$ 秒开始前消失，同时产生 $6$ 个猪分身，其中：

• 有 $1$ 个猪分身会诞生在 $x=i+1$ 处。
• 有 $2$ 个猪分身会诞生在 $x=i+2$ 处。
• 有 $3$ 个猪分身会诞生在 $x=i+3$ 处。

猪想知道，经过 $n$ 秒后，有多少个猪分身曾在 $x=n-1$ 处停留过。

形式化地，设第 $t$ 秒位于 $x=n-1$ 处的猪分身有 $f_t$ 个，求 $\sum\limits_{t=0}^nf_t$。

答案对 $998244353$ 取模。

我们在题目的最后给出了一定的提示。

一行一个整数 $n$（$2\le n\le10^{18}$）。

一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例 1

输入

4

输出

8

解释

下面用 $[g_0,g_1,g_2,g_3,\cdots]$ 来表示 $x=i$ 处有 $g_i$ 个猪分身（$i=0,1,2,3,\cdots$）：

• 第 $0$ 秒，情况是 $[1,0,0,0,\cdots]$。
• 第 $1$ 秒，情况是 $[0,1,2,3,\cdots]$。
• 第 $2$ 秒，情况是 $[0,0,1,4,\cdots]$。
• 第 $3$ 秒，情况是 $[0,0,0,1,\cdots]$。
• 第 $4$ 秒，情况是 $[0,0,0,0,\cdots]$。

所以，答案是 $0+3+4+1+0=8$。

样例 2

输入

10

输出

1331

样例 3

输入

100

输出

252917600

模意义下的加减乘法

设 $p$ 是正整数，容易证明：

快速幂

设 $b$ 是正整数，现欲求 $a^b$。

若 $b$ 很大，则做 $O(b)$ 次乘法是不可接受的。

设 $b$ 的二进制表示为 $\overline{c_tc_{t-1}\cdots c_0}$，其中 $t=\lfloor\log_2b\rfloor$，$c_i=\left\lfloor\dfrac{b}{2^i}\right\rfloor\bmod2$。

由 $a^{2^{i+1}}=a^{2^i}\times a^{2^i}$，先求出 $a^{2^0},a^{2^1},\cdots,a^{2^t}$，则

这样，就只需要做 $O(\log b)$ 次乘法。