CF2084E Blossom

You are given a permutation $ a $ of length $ n $ $ ^{\text{∗}} $ where some elements are missing and represented by $ -1 $ . Define the value of a permutation as the sum of the MEX $ ^{\text{†}} $ of all its non-empty subsegments $ ^{\text{‡}} $ . Find the sum of the value of all possible valid permutations that can be formed by filling in the missing elements of $ a $ modulo $ 10^9 + 7 $ . $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ \bf{0} $ to $ \bf{n - 1} $ in arbitrary order. For example, $ [1,2,0,4,3] $ is a permutation, but $ [0,1,1] $ is not a permutation ( $ 1 $ appears twice in the array), and $ [0,2,3] $ is also not a permutation ( $ n=3 $ but there is $ 3 $ in the array). $ ^{\text{†}} $ The minimum excluded (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 the collection $ c $ . $ ^{\text{‡}} $ A sequence $ a $ is a subsegment of a sequence $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 1000 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 5000 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -1 \le a_i < n $ ). It is guaranteed that the elements of $ a $ that are not $ -1 $ are distinct. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

For each test case, output a single integer — the sum of the value of all possible valid permutations modulo $ 10^9 + 7 $ .

In the first test case, the only valid permutation is $ [0, 1] $ , and the value of $ [0, 1] $ is $ 3 $ since: $ $$$\operatorname{mex}([0]) + \operatorname{mex}([1]) + \operatorname{mex}([0, 1]) = 1 + 0 + 2 = 3 $ $

So the answer is $ 3 $ .

In the second test case, there are two valid permutations: $ \[0, 1\] $ and $ \[1, 0\] $ . The value of $ \[0, 1\] $ and the value of $ \[1, 0\] $ is $ 3 $ , so the answer is $ 3 + 3 = 6 $ .

In the fourth test case, there are two valid permutations: $ \[0, 2, 1\] $ and $ \[1, 2, 0\] $ . The value of $ \[0, 2, 1\] $ is $ 5 $ since:

$ $ \operatorname{mex}([0]) + \operatorname{mex}([2]) + \operatorname{mex}([1]) + \operatorname{mex}([0, 2]) + \operatorname{mex}([2, 1]) + \operatorname{mex}([0, 2, 1]) = 1 + 0 + 0 + 1 + 0 + 3 = 5 $ $

And the value of $ \[1, 2, 0\] $ is $ 5 $ since:

$ $ \operatorname{mex}([1]) + \operatorname{mex}([2]) + \operatorname{mex}([0]) + \operatorname{mex}([1, 2]) + \operatorname{mex}([2, 0]) + \operatorname{mex}([1, 2, 0]) = 0 + 0 + 1 + 0 + 1 + 3 = 5 $ $

So the answer is $ 5 + 5 = 10$$$.