Counting Involutions on a Finite Set

Given a positive integer k, consider the set $$N = \{x \mid x \in \mathbb{N}_+,\, x \le k\}$$. Define a function $$f: N \to N$$ such that for every $$x \in N$$ the condition

holds. Such a function is an involution of the set N.

Your task is to count the number of different functions \( f \) satisfying the above condition. Since the answer can be very large, output the result modulo 14233333.

Note: Any function that satisfies \(f(f(x)) = x\) must be an involution, hence a permutation whose cycles are only of lengths 1 or 2.

inputFormat

The input consists of a single line containing a positive integer k (\(1 \le k \le 10^6\) or as specified by the problem constraints).

outputFormat

Output the number of functions \(f: N \to N\) such that \(f(f(x)) = x\) for every \(x \in N\), taken modulo 14233333.

sample

1

1