Secret Gift Swap With No Self-Match

MediumCombinatoricsDerangementsCountingModular-Arithmetic5 hidden tests

At a party n guests each brought one gift, and the gifts are redistributed so that every guest receives exactly one gift and nobody receives the gift they brought. Count the number of valid redistributions. Report the count modulo 1000000007.

Input format

A single line with one integer n.

Output format

A single integer: the number of redistributions with no self-match, modulo 1000000007.

Constraints

0 <= n <= 1000

Examples

Example 1

Input

Expected

Explanation

There are 9 derangements of 4 items, so the answer is 9.

Example 2

Input

Expected

Explanation

With no guests there is exactly one (empty) redistribution, D(0)=1.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →