Background

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.

Problem Description

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$.

Input Format

A single positive integer $k$.

Output Format

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

3

4

Hint

For $k = 3$, the four mappings are:

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