P6870 [COCI 2019/2020 #5] Zapina

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.

One positive integer: $n$.

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

### 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](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #5](https://hsin.hr/coci/archive/2019_2020/contest5_tasks.pdf) _T5 Zapina_**, translated by [90693](/user/90693)。 Translated by ChatGPT 5