Derangements Problem

Given n letters and n envelopes, determine the number of ways to place the letters into the envelopes such that no letter is placed into its corresponding envelope. This classical problem is known as the derangements problem. The number of derangements \( !n \) can be computed using the formula:

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

inputFormat

The input consists of a single integer \( n \) (where \(1 \leq n \leq 20\)).

outputFormat

Output a single integer that represents the number of derangements for n letters and n envelopes.

sample

1

0