有 $N$ 個正方形，它們的左上及右下角之間有線段連接，把所有正方形連接起來形成下方的圖形 :
現在我們定義 一筆畫 為 : 一個路徑滿足恰走過所有的邊各一次。
現在想問你如果從左上角的位置出發 (也就是紅點的位置) 一筆畫到右下角的位置 (藍點的位置)，有幾種方法數 ? 因為答案可能很大，請模 $998244353$。詳情可參考範例及提示。
輸入有個正整數 $N ( 1 ≤ N ≤ 10^{18} )$，代表正方形的數目。
輸出一筆畫的方法數模 $998244353$。
1
6
2
44
48763
345406998
不公開 測資點#0 (5%): 1.0s , <1K
不公開 測資點#1 (5%): 1.0s , <1K
不公開 測資點#2 (5%): 1.0s , <1K
不公開 測資點#3 (5%): 1.0s , <1K
不公開 測資點#4 (5%): 1.0s , <1K
不公開 測資點#5 (5%): 1.0s , <1K
不公開 測資點#6 (5%): 1.0s , <1K
不公開 測資點#7 (5%): 1.0s , <1K
不公開 測資點#8 (5%): 1.0s , <1K
不公開 測資點#9 (5%): 1.0s , <1K
不公開 測資點#10 (5%): 1.0s , <1K
不公開 測資點#11 (5%): 1.0s , <1K
不公開 測資點#12 (5%): 1.0s , <1K
不公開 測資點#13 (5%): 1.0s , <1K
不公開 測資點#14 (5%): 1.0s , <1K
不公開 測資點#15 (5%): 1.0s , <1K
不公開 測資點#16 (5%): 1.0s , <1K
不公開 測資點#17 (5%): 1.0s , <1K
不公開 測資點#18 (5%): 1.0s , <1K
不公開 測資點#19 (5%): 1.0s , <1K
範例輸入 # 1:
上方是 $N=1$ 的圖形，總共有 $6$ 種走法 :
$A\rightarrow B\rightarrow C\rightarrow A\rightarrow D\rightarrow C$
$A\rightarrow B\rightarrow C\rightarrow D\rightarrow A\rightarrow C$
$A\rightarrow C\rightarrow B\rightarrow A\rightarrow D\rightarrow C$
$A\rightarrow C\rightarrow D\rightarrow A\rightarrow B\rightarrow C$
$A\rightarrow D\rightarrow C\rightarrow A\rightarrow B\rightarrow C$
$A\rightarrow D\rightarrow C\rightarrow B\rightarrow A\rightarrow C$
範例輸入 # 2 :
以下為 $N = 2$ 的圖形，可計算出有 $44$ 種走法。
範例輸入 # 3 :
請記得將答案模 $998244353$ 。
配分 :
$25 \%\ :\ N ≤ 5$
$25 \%\ :\ N ≤ 100$
$50 \%\ :\ $無其他限制