P3795 Zhong's Mapping

In the year 2233, the math teacher and math contest advisor Zhong JG at CSSYZ School is already over 2200 years old. To celebrate the birthday, they gave a problem to the public.

Let $N = M = \left\{x|x\in N_+,x\leq k,k\in N_+\right\}$. Let $f$ be a mapping from $N$ to $M$. Count the number of distinct mappings $f$ that satisfy $f(f(x)) = x$. Since the answer may be large, output the result modulo $14233333$.

A single positive integer $k$.

Output the number of distinct mappings $f$ satisfying $f(f(x)) = x$, modulo $14233333$.

For $k = 3$, the four mappings are: | f(1) | f(2) | f(3) | |-|-|-| | 1 | 2 | 3 | | 1 | 3 | 2 | | 2 | 1 | 3 | | 3 | 2 | 1 | Constraints: - For 20% of the testdata, $1 \leq k \leq 9$. - For the other 80% of the testdata, $1 \leq k \leq 10^7$. Memory 20 MB... (I initially set 1 MB and got myself into trouble). Translated by ChatGPT 5