Count Good Permutations

This problem requires you to compute the number of good permutations (also known as derangements) for a permutation of length \( n \).

A permutation \( \pi \) of \( \{1,2,\ldots,n\} \) is considered good if no element appears in its original position. In other words, for all indices \( i \), \( \pi(i) \neq i \).

The number of derangements \( d(n) \) can be computed using the recurrence relation:

\( d(n) = (n-1)\left(d(n-1) + d(n-2)\right) \),

with the initial conditions \( d(0)=1 \) and \( d(1)=0 \). Your task is to implement this calculation.

inputFormat

The input consists of a single line containing an integer \( n \) that represents the length of the permutation.

outputFormat

Output a single integer, which is the number of good permutations (derangements) for the given \( n \).

0

1