 # Finding number of permutation of size N identical to original Array A on applying a function on all

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)
• MEX(0, 2, 3) = MEX(0, 3, 2) = 1 (For subarray A, A, A
• MEX(3, 1) = MEX(2, 1) = 0 ( For subarray A, A)
• MEX(0, 2, 3, 1) = MEX(0, 3, 2, 1) = 4 For subarray A, A. A A Similarly we can check for every subarray.