Count Derangements

You are given an integer n and are required to compute the number of derangements of a set of size n. A derangement is a permutation where no element appears in its original position. The number of derangements, denoted as \( D(n) \), satisfies the recurrence relation:

\( D(n) = (n-1) \times (D(n-1) + D(n-2)) \)

with base cases:

• \( D(0) = 1 \)
• \( D(1) = 0 \)

Read the input from stdin and output the answer to stdout.

inputFormat

The input consists of a single integer n (0 ≤ n ≤ 20) provided from stdin.

outputFormat

Output a single integer representing the number of derangements for the given n to stdout.

3

2