CF2208E Counting Cute Arrays

Let $ [A_1, A_2, \ldots, A_n] $ be an array of $ n $ positive integers. Define array $ f(A) $ as followed: For each integer $ i $ from $ 1 $ to $ n $ : - If there exists integer $ j $ such that $ j \lt i $ and $ A_j \lt A_i $ , $ f(A)_i=\max\limits_{j \lt i,A_j \lt A_i} j $ . That is, $ f(A)_i $ is the index of the rightmost element before $ i $ whose value is strictly smaller than $ A_i $ . - Otherwise $ f(A)_i=0 $ . We call the array $ [P_1,P_2,\ldots,P_n] $ of non-negative integers a cute array if there exists an array $ A $ such that $ f(A)=P $ . Given a length $ n $ array $ X $ in which $ -1\le X_i\le n $ holds for all $ i $ from $ 1 $ to $ n $ . Count the numbers of cute arrays $ X' $ formed by replacing the $ -1 $ s in $ X $ with integers from $ 0 $ to $ n $ . As the number can be very large, print it modulo $ 998\,244\,353 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows. The first line of each test cases contain an integer $ n $ ( $ 1\le n\le5000 $ ) denoting the length of $ X $ . The second line contain $ n $ integers $ X_1,X_2,\ldots,X_n $ ( $ -1\le X_i\le n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

For each test cases, output a single integer denoting the number of arrays $ X' $ such that $ X' $ is a cute array, modulo $ 998\,244\,353 $ .

For the first test case, only $ [0,0,0] $ and $ [0,0,2] $ are cute arrays among all possible $ X' $ . $ [0,0,0] $ is a good cute array because $ f([1,1,1])=[0,0,0] $ , and $ [0,0,2] $ is a good array because $ f([1,1,2])=[0,0,2] $ . For the second test case, only $ [0,1,1,0] $ , $ [0,1,1,1] $ and $ [0,1,1,3] $ are cute arrays among all possible $ X' $ .