Counting Colored DAGs with Outdegree and Indegree Constraints

You are given a directed acyclic graph (DAG) with n vertices labeled from 1 to n. Each edge in the graph is assigned one of k different colors. The graph satisfies the following two properties:

• Each vertex has at most one outgoing edge.
• The indegree of every vertex is an element of a given set S.

Recall that the indegree of a vertex is the number of edges directed into it. By convention, vertex 1 has indegree 0 because no vertex comes before it in any topological ordering. Also, note that since each vertex can have at most one outgoing edge and every edge goes from a vertex to a vertex with a larger label (to ensure acyclicity), an assignment of edges is uniquely determined by the decisions made at vertices 1 through n-1 (vertex n cannot have any outgoing edge).

Your task is to count the number of such graphs modulo 998244353. Two graphs are considered different if and only if there exists a directed edge from some vertex a to some vertex b that appears in exactly one of the graphs, or it appears in both graphs but its color is different.

Important: All formulas must use LaTeX formatting. For example, the modulus should be written as \(998244353\), the number of vertices as \(n\), the number of colors as \(k\), etc.

inputFormat

The input consists of two lines:

1. The first line contains three integers \(n\), \(k\), and \(|S|\) — the number of vertices, the number of different colors, and the size of the set \(S\), respectively.
2. The second line contains \(|S|\) space-separated integers, representing the allowed indegree values (the set \(S\)).

outputFormat

Output a single integer: the number of valid graphs modulo \(998244353\).

sample

3 2 2
0 1

11