DFS 트리 개수 세기

깊이 우선 탐색(DFS)이라는 트리 순회 알고리즘을 공부하고 있다. 노드가 $n$개이고 깊이가 $K$인 루트 트리를 생각하자. 노드는 1부터 $n$까지, 깊이는 1부터 $K$까지 번호가 붙어 있다. 루트(깊이 1의 노드)는 노드 1이다. 모든 잎은 같은 깊이, 즉 깊이 $K$에 있다. 노드 $i$는 자식 노드들의 배열 $c_i$를 가지며, $i$가 잎이면 이 배열은 비어 있을 수 있다. 알고리즘의 의사 코드는 다음과 같다.

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

그림의 트리에서 DFS(1, 1)의 반환값은 왼쪽 트리가 $[1, 2, 3, 3, 3]$, 오른쪽 트리가 $[1, 2, 3, 2, 3]$이다.

$f_K(n)$을 노드가 $n$개이고 모든 잎이 깊이 $K$에 있는 모든 트리에 걸쳐, DFS(1, 1)이 가질 수 있는 서로 다른 반환값의 개수로 정의한다. 정수 $M$개 $A_1, A_2, \dots, A_M$이 주어질 때, $f_K(A_1) \times f_K(A_2) \times \cdots \times f_K(A_M)$의 값을 $998\,244\,353$으로 나눈 나머지를 구하라.

첫 줄에 두 정수 $K$와 $M$이 주어진다($1 \le K, M \le 100\,000$). 둘째 줄에는 $M$개의 정수 $A_1, A_2, \dots, A_M$이 주어진다($K \le A_i \le 200\,000$).

$f_K(A_1) \times f_K(A_2) \times \cdots \times f_K(A_M)$의 값을 $998\,244\,353$으로 나눈 나머지를 출력한다.