問題文

将棋には銀将というコマがあり、以下のような動きをします。

これを無限に広がる二次元平面上で動かしてみましょう。

銀将が座標 $(x,y)$ に置かれている時、あなたは $1$ 回の操作で以下の $5$ つの座標のうちいずれかに銀将を動かせます (これは上の図に対応します)。

• $(x,y+1)$
• $(x+1,y+1)$
• $(x-1,y+1)$
• $(x+1,y-1)$
• $(x-1,y-1)$

今、二次元平面上の原点に銀将が置かれています。$K$ 回以下の操作で銀将が到達できる座標はいくつありますか？

入力

$K$

• $1\le K\le {10}^9$
• $K$ は整数

出力

$K$ 回以下の操作で銀将が到達できる座標の数を出力してください。

サンプル

1

6

3

38

998244353

3985967153185554438