Derangements: Counting Gift Exchanges

In many gift exchange scenarios, it is important to count the number of ways to redistribute gifts so that no one receives his or her own gift. This problem is about counting the number of derangements of n items. A derangement is a permutation where none of the elements appears in its original position.

The derangement numbers \(D(n)\) can be computed using the recurrence relation:

[ D(n) = (n-1)\bigl(D(n-1) + D(n-2)\bigr), \quad \text{with} \quad D(0)=1 \quad \text{and} \quad D(1)=0. ]

Your task is to write a program that, given an integer n, computes \(D(n)\). You must read the input from standard input (stdin) and write your output to standard output (stdout).

inputFormat

A single integer n ((0 \le n \le 20)) is provided as input from stdin.

outputFormat

Output the number of derangements for the given integer n to stdout.## sample

0

1