Biological Software Utilities

Time limit1sMemory limit512 MB

Summary

Count the labeled trees on n vertices that have a perfect matching, modulo 998244353, for n up to 10^6.

Level: Hard8 of 10
Topics: Combinatorics, Tree, Math, Dynamic programming
Solved: No attempts yet

Problem

You are developing a software kit named Biological Software Utilities (BSU). The kit includes a program dedicated to tree recognition. Recall that a tree is a connected undirected graph without cycles.

In nature, when a tree grows, two neighboring vertices are added at the same time. Thus, you consider a tree to be plausible if, after removing some edges, the resulting graph consists only of connected components with $2$ vertices. In other words, a tree is plausible if and only if it has a perfect matching.

Now you are to implement a new function for BSU to calculate the number of plausible trees that have $n$ vertices numbered with distinct integers between $1$ and $n$ . Two trees are considered different if there is an edge $(u, v)$ which is present in exactly one of the trees.

Since the number of plausible trees can be very large, you have to calculate it modulo $998\,244\,353$ .

Input

The only line contains an integer $n$ , the number of vertices in a tree ( $1 \le n \le 10^6$ ).

Output

Print the number of plausible trees with $n$ vertices modulo $998\,244\,353$ .

Examples5

Example 1
Input
```
1
```
Expected output
```
0
```
Example 2
Input
```
2
```
Expected output
```
1
```
Example 3
Input
```
3
```
Expected output
```
0
```
Example 4
Input
```
4
```
Expected output
```
12
```
Example 5
Input
```
7788
```
Expected output
```
178152092
```