꽃 배달

아가씨 토노 한나는 소중한 여동생과 함께 살고 있다. 한나가 살고 있는 도시는 $N$개의 정점으로 이루어진 트리 형태를 하고 있으며, 한나의 집은 $1$번 정점에 위치하고 있다. 도시의 $1$번 정점이 아닌 모든 리프에는 꽃집이 $1$곳씩 존재하고 있으며, 꽃집의 총 개수를 $K$라고 하였을 때 $K \leq 22$를 만족한다. 또한, $1$번 정점과 꽃집이 있는 정점을 제외한 각 $i$번 정점에는 꽃이 $a_i$개씩 피어 있다.

한나는 집에 혼자 있을 여동생이 걱정되어 모든 꽃집에 꽃을 최대한 빨리 배달하고자 한다. 한나는 처음에 $1$번 정점에서 출발하며, 아직 방문하지 않은 꽃집이 있는 동안 다음과 같은 과정으로 이동을 반복한다.

• 아직 방문하지 않은 꽃집 하나를 선택한다.
• 현재 위치에서 선택한 꽃집까지 최단 경로를 따라 이동한다. 이동 중 지나가는 정점에 아직 따지 않은 꽃이 있다면 모두 딴다. 한 번 딴 꽃은 다시 딸 수 없다.
• 꽃집에 도착하면 지금까지 따서 가지고 있는 꽃 중 정확히 한 개를 판다. 가지고 있는 꽃이 없다면 이 꽃집에 꽃을 팔 수 없다.

한나는 모든 꽃집들에 꽃을 팔아서 돈을 벌어야 한다. 모든 꽃집에 꽃을 팔 수 있는 꽃집 방문 순서를 성공적인 방문 순서라고 하자. 가능한 꽃집 방문 순서 $K!$개 중에서 성공적인 방문 순서의 개수를 $998\,244\,353$으로 나눈 나머지를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $a_1\ a_2\ \cdots\ a_N$

성공적인 방문 순서의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

• $2 \le N \le 200\,000$.
• $0 \le a_i \le 10^9$ ().