Two integer sequences are defined for n >= 1 by

a_n = 2 a_{n-1} + b_{n-1}

b_n = a_{n-1} + b_{n-1}

with a_0 = 1 and b_0 = 0.

Compute a_n modulo 998244353.

Input

One line with the integer n.

Output

a_n modulo 998244353.

Constraints

0 <= n <= 10^18

Scoring

This is a standard problem: a submission scores full points if it produces the correct output for every test case, and zero otherwise.