O Xor Triangle

制限時間: 2 sec メモリ制限: 1024 MB

Xor triangle

Statement

正整数 \(N\) が与えられます．

\(1\) 以上 \(2^N\) 未満の整数の組 \((a,b)\) であって，以下の条件を満たすものの個数を素数 \(998244353\) で割ったあまりを求めてください．

ただし，整数 \(x,y\) に対し，\(x\oplus y\) で \(x,y\) のビット単位 XOR を表します．

Input

\(1\) 行に整数 \(N\) が与えられる。( \(1 \leq N \leq 10^{18}\) )

Output

条件を満たす整数の組 \((a,b)\) の個数を素数 \(998244353\) で割ったあまりを出力せよ。

Examples

Input 1

Output 1

Input 2

Output 2

Input 3

Output 3

851087540

Note

\(2\) つ目のサンプルについて、例えば \((a,b)=(13,24)\) は条件を満たします。 \(a \oplus b = 13 \oplus 24 = 21\) であり、 \(3\) 辺の長さが \(13,24,21\) であるような非退化な三角形が存在します。

条件を満たす整数の組 \((a,b)\) は全部で \(390\) 個存在します。

非負整数 \(x,y\) のビット単位 XOR \(x \oplus y\) は以下のように定義されます。

\(x \oplus y\)を二進表記した際の \(2^k \ (k \geq 0)\) の位の数は、\(x,y\) を二進表記した際の \(2^k\) の位の数のうち丁度一方が \(1\) であれば \(1\)、そうでなければ \(0\) である。

例えば、\(3 \oplus 5 = 6\) となります(二進表記すると \(011 \oplus 101 = 110\) )。