Counting Happy Assignments

There are n distinct people and n distinct problems. Person i is happy if and only if they are assigned problem i. In other words, an assignment scheme is a permutation of n elements, and a person is happy if they form a fixed point in that permutation.

Your task is to compute the number of assignment schemes where at least one person is happy. Note that the total number of assignments is n! and the number of assignments where nobody is happy (i.e. derangements) is D(n). Thus, the answer is given by:

$$\text{Answer} = n! - D(n),$$

where the number of derangements can be computed by the recurrence:

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

inputFormat

The input consists of a single integer n (1 ≤ n) representing the number of people (and problems).

outputFormat

Output a single integer representing the number of assignment schemes where at least one person is happy.

sample

1

0