I. Inclusion and Diversity
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Iceberg Corporation is desired by many working students thanks to its smart ad strategies. Each year, Yessine will get a very large pool of (unpaid) internship applicants. Usually, Yessine will only select beautiful girls without reading any resumes. However, this year, he has heard that companies with diversity and inclusion are more likely to attract investors. So, he decided to include people from different ethnicities.

To select candidates, Yessine has prepared a list of $$$m$$$ minority groups. For each minority, each candidate either belongs or doesn't belong to that minority group.

To maximize diversity, Yessine will select candidates in such a way that no applicant is more diverse than another one. However, if two or more candidates are equally diverse, then Yessine will only select one of them.

A candidate $$$A$$$ is more diverse than $$$B$$$ if the set of minority groups of $$$B$$$ is included in the set of minority groups of $$$A.$$$ Two candidates are equally diverse if they belong to exactly the same minority groups.

Now, 2024 is the year of diversity and inclusion, and Yessine wants to attract more investors. For that reason, he will maximize the number of interns. But still, he will keep in his selection criteria both conditions stated above.

The application pool is very large, and it contains every possible set of minority groups. What is the maximal number of applications Yessine can accept under both criteria. Since the answer can be large, output it modulo $$$M=998'244'353$$$

Input

The input contains one integer $$$1 \le m \le 4\times 10^{3}:$$$ The number of minority groups.

Output

Output one integer, representing the desired answer modulo $$$998'244'353$$$

Examples
Input
1
Output
1
Input
2
Output
2
Input
3
Output
3
Input
1936
Output
794915107
Input
2024
Output
109427260
Note

In the second test case, we have two minority groups. Let's say they are $$$\{\text{Asian}, \text{Hispanic}\}.$$$ We have $$$4$$$ possible profiles in total: $$$\{\}, \{\text{Asian}\},\{\text{Hispanic}\}, \{\text{Asian},\text{Hispanic}\}.$$$ Yessine can select at most $$$2$$$ candidates under his criteria, the first belongs to minority groups $$$\{\text{Asian}\},$$$ and the second belongs to minority groups $$$\{\text{Hispanic}\}.$$$ Remember that the existence of candidates belonging to any mix of these minorities is guaranteed.

For the third test case, Let $$$\{\text{Asian},\text{Hispanic},\text{Middle Eastern}\}$$$ be the set of minority groups. Yessine can select $$$3$$$ candidates with the following respective profiles: $$$\{\text{Asian}\},\{\text{Hispanic}\},\{\text{Middle Eastern}\}.$$$ It can be proven that he cannot select more under his criteria.