Description

There are $n$ distinct people and $n$ distinct problems.

The $i$-th person is happy if and only if they are assigned $i$ problems.

Find the number of assignment plans that make at least one person happy.

Input Format

One positive integer: $n$.

Output Format

One number: your answer $\bmod(10^9+7)$.

1

1

2

3

314

192940893

Hint

Constraints

This problem uses bundled testdata.

• For $22$ pts of testdata, $2\leq n\leq 7$.
• For another $33$ pts of testdata, $1\leq n\leq 20$.
• For all testdata, $1\leq n\leq 350$.

Sample #2 Explanation

There are the following $3$ plans:

• Give the first problem to the first person, and the second problem to the second person.

• Give the second problem to the first person, and the first problem to the second person.

• Give both problems to the second person.

Notes

Translated from COCI2019-2020 CONTEST #5 T5 Zapina, translated by 90693。

Translated by ChatGPT 5