CF2169F Subsequence Problem

Given three integers $ n, m, k $ , as well as $ k $ arrays of integers of lengths $ l_1, l_2, \dots, l_k $ respectively. We denote the element at position $ j $ in array number $ i $ as $ a_{i,j} $ . In each array, all elements are distinct (but may repeat in different arrays). We call an array $ b $ of length $ k $ beautiful if for each $ i $ from $ 1 $ to $ k $ , the element $ b_i $ is equal to one of the elements of the array $ a_i $ . We call an array $ c $ perfect if every beautiful array $ b $ can be obtained from array $ c $ by deleting several (possibly zero) elements without changing their order. In other words, array $ c $ is perfect if every beautiful array $ b $ is a subsequence of it. Your task is to count the number of perfect arrays $ c $ of length $ n $ containing only integers from $ 1 $ to $ m $ .

The first line contains three integers $ n, m, k $ ( $ 2 \le n \le 2 \cdot 10^5 $ ; $ 5 \le m \le 10^8 $ ; $ 2 \le k \le n $ ). The second line contains $ k $ integers $ l_1, l_2, \dots, l_k $ ( $ 1 \le l_i \le 5 $ ). The following $ k $ lines contain the $ i $ -th line with $ l_i $ distinct integers $ a_{i,1}, a_{i,2}, \dots, a_{i,l_i} $ ( $ 1 \le a_{i,j} \le m $ ). Additional constraint on the input: the sum of $ l_i $ does not exceed $ n $ .

Print one integer — the number of perfect arrays of length $ n $ such that they contain only integers from $ 1 $ to $ m $ . Since the answer may be very large, output it modulo $ 998244353 $ .

In the first example, there are two beautiful arrays: $ [4, 1, 4] $ and $ [4, 1, 3] $ . Only two arrays of length $ 4 $ contain both of these arrays as subsequences: $ [4, 1, 4, 3] $ and $ [4, 1, 3, 4] $ . In the second example, there is only one beautiful array: $ [5, 2] $ . There are $ 13 $ arrays of length $ 3 $ with integers from $ 1 $ to $ 5 $ that contain it as a subsequence.