Mex Permutations#231
Initially, there is an array of integers. It is known, that all its elements are in range [0;n-1] and they are pairwise distinct. In other words, is a permutation.
Let's denote the minimal non-negative integer that does not belong to the set . For example, mex(\{1,2,3\}) = , mex(\{0,1,3\}) = , mex(\{0,1,2\}) = .
Array is being built in such a way, that F_i = mex (a_1, a_2, \dots, a_{i-1}, a_i). Let's denote = .
It is quite easy to build array by given array , but unfortunately, array was lost. You wanted to restore it using array , but there appeared to be too many possible arrays. You want to know how many arrays exists, such that = modulo .
The first line of input contains one integer (1 \le n \le 10^6) — length of the permutation.
The second line of input contains integers F_i (0 \le F_i \le n+1) — elements of array .
Print one integer — number of arrays that satisfy = modulo .
Example 1
Example 2
Example 3
( points): F_i = n+1;
( points): F_i < F_{i+1} for all i < n;
( points): n \le 3;
( points): n \le 7;
( points): n \le 18;
( points): n \le 1000;
( points): no additional restrictions.