Derangements under Modulo 998244353

Given an integer (n) and a permutation of (n) integers, count the number of permutations of size (n) such that no integer remains in its original position (i.e. a derangement). The answer should be computed modulo (998244353). The recurrence relation used in the derangement calculation is given by [ D(n)=(n-1)(D(n-1)+D(n-2)) ] with base cases (D(1)=0) and (D(2)=1).

Note: Although the input contains a permutation sequence, the actual values do not affect the calculation.

inputFormat

The input is read from standard input and consists of two lines. The first line contains a single integer (n) (the size of the permutation). The second line contains (n) space-separated integers representing the permutation sequence.

outputFormat

Output a single integer — the number of derangements of the permutation of size (n), computed modulo (998244353).## sample

3
1 2 3

2