解题思路

把“切一刀”的过程抽象为对每个等边三角形连中点，得到 4 个更小的等边三角形。 若父三角形朝上（记为上三角形 U），切完后得到 3 个上 + 1 个下； 若父三角形朝下（记为下三角形 D），切完后得到 3 个下 + 1 个上。

设第 n 轮后上、下三角形个数分别为 U_n, D_n，初始 U_0=1, D_0=0。则有线性递推：

题目内容

牛牛非常喜欢做饭，并且他尤其喜欢切菜，

不过比起切菜，他更喜欢切三角形，

对于一个正三角形，牛牛喜欢这样切

(我们认为切完之后的三角形也都是正三角形，出题人绘画水平有限)

对于切完之后的三角形，根据三角形的形状，我们认为这个大的三角形由 $3$ 个上三角形和 $1$ 个下三角形构成

牛牛还没有过瘾，他打算对初始三角形切割 $N$ 轮，对于每一轮，他会把所有的小三角形都切开

现在牛牛想知道，经过 $N$ 轮切割后的大三角形中有多少下三角形

输入描述

一个整数N，表示切割轮数 $0≤N≤10^9$

输出描述

一个整数N表示答案 答案可能很大，请输出对998244353取模的结果

样例1

输入

1

输出

1

样例2

输入

2

输出

6

说明