Candy Swap Derangements

Little W bought n pieces of wedding candy and gave them to n people, where each candy has a unique type. Suddenly, Little W wondered: if these n people exchange candies among themselves, in how many ways can this be done so that every person ends up with a candy of a different type than the one they originally received?

A valid exchange plan is a permutation p of the set {1, 2, …, n} such that for every person i, the candy they receive originally belonged to person p(i) whose candy type is different from person i's original candy type. Since all candy types are distinct, this condition is equivalent to requiring that p(i) ≠ i for every i. Such permutations are known as derangements.

The derangement number can be expressed in closed form as:

$$D(n) = n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}$$

or computed via the recurrence:

$$D(0) = 1,\quad D(1) = 0,\quad D(n) = (n-1)[D(n-1) + D(n-2)] \text{ for } n\ge2. $$

inputFormat

The input consists of a single integer n (n ≥ 1), which represents the number of candies (and people).

outputFormat

Output a single integer — the number of valid exchange schemes (i.e. the number of derangements).

sample

1

0