33114번 - Count DFS Tree 다국어

문제

You are currently studying a tree traversal algorithm called the Depth First Search (DFS). Suppose you have a rooted tree of $n$ nodes (numbered from 1ドル$ to $n$) with a depth of $K$ (numbered from 1ドル$ to $K$). The root (the node at depth 1ドル$) is located at node 1ドル$. All leaves are located at the same depth, that is, at depth $K$. Node $i$ has an array of children nodes $c_i,ドル which could be empty if $i$ is a leaf node. The pseudocode of the algorithm is presented as follows.

DFS(u, depth):
 let res be an empty array
 append depth to res
 for each v in c[u]:
 let D be an array initialized with DFS(v, depth + 1)
 for each x in D:
 append x to res
return res

Consider the trees in the following illustration. The return values of DFS(1, 1) for the tree on the left and the tree on the right are $[1, 2, 3, 3, 3]$ and $[1, 2, 3, 2, 3],ドル respectively.

Denote $f_K(n)$ as the number of distinct return values of DFS(1, 1) across all trees consisting of $n$ nodes and all leaves are located in depth $K$. You are given $M$ integers: $A_1, A_2, \dots , A_M$. Determine the value of $f_K(A_1) \times f_K(A_2) \times \cdots \times f_K(A_M)$. As the answer can be very large, find the answer modulo 998ドル,円 244,円 353$.

입력

The first line consists of two integers $K$ $M$ (1ドル ≤ K, M ≤ 100,円 000$).

The following line consists of $M$ integers $A_i$ ($K ≤ A_i ≤ 200,円 000$).

출력

Output a single integer representing the value of $f_K(A_1) \times f_K(A_2) \times \cdots \times f_K(A_M)$ modulo 998ドル,円 244,円 353$.

제한

힌트