You are given a permutation A of size N consisting of only distinct numbers from 0 to N-1. MEX(A1, A2, , Ak) is defined as the smallest non-negative integer that does not include in A1, A2, • • • , Ak A permutation P of size N is said to be identical to A if MEX of every subarray of A is equal to MEX of every subarray of P. More formally:- MEX(AL, AL+1, • • • , AR) = MEX(PL, PL+1 • • • PR) where 1 <= L <= R <= N
Count the number of permutations of size N Identical to A modulo 10** 9 + 7 (the remainder when divided by 10** 9 + 7). Notes • Assuming 1-based indexing. • A subarray is the sequence of the consecutive element of the array. • A permutation of size N is an array consisting of N distinct integers from 0 to N-1
Example->
N = 4
A = [0, 2, 3, 1]
Approach
There are two permutation. P1= [0, 2. 3, 1] and P2 = [0, 3, 2, 1] are identical to A.
For permutation P2 we can see that the MEX of any subarray is equal to the corresponding subarray of A. For example
• MEX(2) = MEX(3) = 0 (for subarray A[2])
• MEX(0, 2, 3) = MEX(0, 3, 2) = 1 (For subarray A[1], A[2], A[3]
• MEX(3, 1) = MEX(2, 1) = 0 ( For subarray A[3], A[4])
• MEX(0, 2, 3, 1) = MEX(0, 3, 2, 1) = 4 For subarray A[1], A[2]. A[3] A[4] Similarly we can check for every subarray.
Thus answer is 2