Sum of Even Binomial Coefficients

Today, Xiao Ming studied combinatorics and is curious about the sum of binomial coefficients for even indices. Given a non-negative integer \( n \), you are to compute

\[ S = \sum_{\substack{0 \le i \le n \\ i\;\text{is even}}} {n \choose i} \]

Recall that \({n \choose i}\) represents the number of ways to choose \( i \) items from \( n \) items without regard to order.

It can be shown using the binomial theorem that for \( n>0 \), \[ S = \frac{1}{2} \left((1+1)^n + (1-1)^n\right) = 2^{n-1}. \] For the special case \( n=0 \), note that \( S = 1 \) (since \({0 \choose 0} = 1\)).

Since the answer may be very large, output the result modulo \(6662333\).

inputFormat

The input consists of a single non-negative integer \( n \) (\(0 \le n\)).

outputFormat

Output the value of \( S \) modulo \(6662333\).

sample

0

1