Chess Pieces Placement with Obstacles

You are given an \(N \times N\) board. In each row there is exactly one obstacle, and no two obstacles share the same column. You need to place \(N\) chess pieces on the board such that:

• You cannot place a piece on a cell containing an obstacle.
• Each row contains exactly one chess piece.
• Each column contains exactly one chess piece.

Let the obstacle in row \(i\) be located at column \(a_i\). Since all obstacles are in distinct columns, the set \(\{a_1, a_2, \dots, a_N\}\) is a permutation of \(\{1,2,\dots, N\}\). Placing the chess pieces is equivalent to finding a permutation \(p\) of \(\{1,2,\dots, N\}\) such that for every \(i\), \(p(i) \neq a_i\). In other words, the answer is the number of derangements of \(N\) items.

The number of derangements \(!N\) can be computed using the formula:

[ !N = \sum_{i=0}^{N} (-1)^i \cdot \binom{N}{i} \cdot (N-i)! ]

Your task is to compute \(!N\) for the given board configuration.

inputFormat

The first line contains an integer \(N\) (\(1 \leq N \leq 20\)), representing the size of the board.

The second line contains \(N\) space-separated integers \(a_1, a_2, \dots, a_N\) where \(a_i\) (\(1 \leq a_i \leq N\)) is the column of the obstacle in the \(i\)-th row. It is guaranteed that all \(a_i\) are distinct.

outputFormat

Output a single integer representing the number of valid ways to place the chess pieces.

sample

3
2 3 1

2