Gift Exchange

Time limit2sMemory limit128 MB

Summary

Compute the number of derangements of N items modulo 1,000,000,000.

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

Problem

Every participant in an event prepared exactly one gift.

After the event, the gifts will be handed out among the participants. Each participant must receive exactly one gift, and nobody may receive the gift they prepared.

Find the number of ways to hand out the gifts while satisfying these conditions.

Input

The first line contains the number of participants N. (1 ≤ N ≤ 1,000,000)

Output

Print the number of valid gift assignments modulo 1,000,000,000 on the first line.

Examples4

Example 1
Input
```
5
```
Expected output
```
44
```
Example 2
Input
```
4
```
Expected output
```
9
```
Example 3
Input
```
3
```
Expected output
```
2
```
Example 4
Input
```
21
```
Expected output
```
50944540
```