Sequence Operations and Product Modulo Computation

We are given an infinite sequence \(\{a\}\) with indices starting from \(1\). Initially, \(a_1=1\) and \(a_i=0\) for all \(i\ge2\). You need to perform \(m\) operations on the sequence. Each operation consists of the following two phases:

• For every odd index \(i\), update \(a_{i+1} \gets a_{i+1}+a_i\).
• For every even index \(i\), update \(a_{i+1} \gets a_{i+1}+a_i\).

After all operations are performed, you are required to output the value of \[ \left(\prod_{i = 1}^{m} (a_i + 1)\right)\bmod 998244353, \] where \(m\) is the number of operations. Note that the product is taken over the first \(m\) elements of the final sequence.

inputFormat

The input contains a single integer \(m\) (\(1 \le m\le \text{some upper limit}\)) representing the number of operations.

outputFormat

Output a single integer which is the value of \(\left(\prod_{i = 1}^{m} (a_i + 1)\right)\bmod 998244353\) computed after performing all operations.

sample

1

2