Counting Derangements

In this problem, you are given an integer N representing the number of items. Your task is to calculate the number of derangements (i.e. permutations in which no element appears in its original position) for these N items.

A derangement is defined by the recurrence relation:

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

with the initial conditions defined as:

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

For example, if N = 3, the number of derangements is 2.

inputFormat

The input consists of a single integer N given via standard input.

Constraints:

• 0 \(\leq N \leq 10^5\)

outputFormat

Output a single integer representing the number of derangements for N items. The result should be printed to standard output.

## sample

3

2