CF1677D Tokitsukaze and Permutations

Tokitsukaze has a permutation $ p $ . She performed the following operation to $ p $ exactly $ k $ times: in one operation, for each $ i $ from $ 1 $ to $ n - 1 $ in order, if $ p_i $ > $ p_{i+1} $ , swap $ p_i $ , $ p_{i+1} $ . After exactly $ k $ times of operations, Tokitsukaze got a new sequence $ a $ , obviously the sequence $ a $ is also a permutation. After that, Tokitsukaze wrote down the value sequence $ v $ of $ a $ on paper. Denote the value sequence $ v $ of the permutation $ a $ of length $ n $ as $ v_i=\sum_{j=1}^{i-1}[a_i < a_j] $ , where the value of $ [a_i < a_j] $ define as if $ a_i < a_j $ , the value is $ 1 $ , otherwise is $ 0 $ (in other words, $ v_i $ is equal to the number of elements greater than $ a_i $ that are to the left of position $ i $ ). Then Tokitsukaze went out to work. There are three naughty cats in Tokitsukaze's house. When she came home, she found the paper with the value sequence $ v $ to be bitten out by the cats, leaving several holes, so that the value of some positions could not be seen clearly. She forgot what the original permutation $ p $ was. She wants to know how many different permutations $ p $ there are, so that the value sequence $ v $ of the new permutation $ a $ after exactly $ k $ operations is the same as the $ v $ written on the paper (not taking into account the unclear positions). Since the answer may be too large, print it modulo $ 998\,244\,353 $ .

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. Each test case consists of two lines. The first line contains two integers $ n $ and $ k $ ( $ 1 \leq n \leq 10^6 $ ; $ 0 \leq k \leq n-1 $ ) — the length of the permutation and the exactly number of operations. The second line contains $ n $ integers $ v_1, v_2, \dots, v_n $ ( $ -1 \leq v_i \leq i-1 $ ) — the value sequence $ v $ . $ v_i = -1 $ means the $ i $ -th position of $ v $ can't be seen clearly. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case, print a single integer — the number of different permutations modulo $ 998\,244\,353 $ .

In the first test case, only permutation $ p=[5,4,3,2,1] $ satisfies the constraint condition. In the second test case, there are $ 6 $ permutations satisfying the constraint condition, which are: - $ [3,4,5,2,1] $ $ \rightarrow $ $ [3,4,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [3,5,4,2,1] $ $ \rightarrow $ $ [3,4,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [4,3,5,2,1] $ $ \rightarrow $ $ [3,4,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [4,5,3,2,1] $ $ \rightarrow $ $ [4,3,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [5,3,4,2,1] $ $ \rightarrow $ $ [3,4,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [5,4,3,2,1] $ $ \rightarrow $ $ [4,3,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ So after exactly $ 2 $ times of swap they will all become $ a=[3,2,1,4,5] $ , whose value sequence is $ v=[0,1,2,0,0] $ .