CF1699C The Third Problem

You are given a permutation $ a_1,a_2,\ldots,a_n $ of integers from $ 0 $ to $ n - 1 $ . Your task is to find how many permutations $ b_1,b_2,\ldots,b_n $ are similar to permutation $ a $ . Two permutations $ a $ and $ b $ of size $ n $ are considered similar if for all intervals $ [l,r] $ ( $ 1 \le l \le r \le n $ ), the following condition is satisfied: $ $$$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]), $ $ where the $ \\operatorname{MEX} $ of a collection of integers $ c\_1,c\_2,\\ldots,c\_k $ is defined as the smallest non-negative integer $ x $ which does not occur in collection $ c $ . For example, $ \\operatorname{MEX}(\[1,2,3,4,5\])=0 $ , and $ \\operatorname{MEX}(\[0,1,2,4,5\])=3 $ .

Since the total number of such permutations can be very large, you will have to print its remainder modulo $ 10^9+7 $ .

In this problem, a permutation of size $ n $ is an array consisting of $ n $ distinct integers from $ 0 $ to $ n-1 $ in arbitrary order. For example, $ \[1,0,2,4,3\] $ is a permutation, while $ \[0,1,1\] $ is not, since $ 1 $ appears twice in the array. $ \[0,1,3\] $ is also not a permutation, since $ n=3 $ and there is a $ 3$$$ in the array.

N/A

N/A

For the first test case, the only permutations similar to $ a=[4,0,3,2,1] $ are $ [4,0,3,2,1] $ and $ [4,0,2,3,1] $ . For the second and third test cases, the given permutations are only similar to themselves. For the fourth test case, there are $ 4 $ permutations similar to $ a=[1,2,4,0,5,3] $ : - $ [1,2,4,0,5,3] $ ; - $ [1,2,5,0,4,3] $ ; - $ [1,4,2,0,5,3] $ ; - $ [1,5,2,0,4,3] $ .