잊혀진 땅

Fyteland의 과학자들은 역사 연구를 좋아하기로 유명하다. 최근 이들은 위대한 과거 문명에 속했음이 확실한 n개 도시의 유적을 발견했다.

발견된 모든 도시는 정확히 n − 1개의 도로로 연결되어 있었고, 이 도로들로 임의의 두 도시 사이를 이동하는 방법은 정확히 하나뿐이었다. 과학자들은 각 도시에서 많은 기록을 찾아냈고, 그 문명의 사람들이 k개의 서로 다른 언어를 사용했다고 결론지었다. 도시 v에서는 언어 av를 사용했다.

도시들은 여러 동맹을 이루고 있었고, 각 도시는 정확히 하나의 동맹에 속했다. 그러나 동맹이 정확히 어떻게 구성되었는지는 알려지지 않았다.

동맹이란 도로로 연결되어 있을 수도 있고 아닐 수도 있는 임의의 도시 집합 c1, c2, . . . , cm을 말한다. 동맹을 다스리려면 서로 다른 언어를 사용하는 사람들이 있는 서로 다른 도시 사이를 연결할 수 있어야 했다. 동맹의 우두머리는 동맹의 어떤 도시 ci에서 사용되거나, 동맹의 두 도시 ci와 cj 사이 최단 경로 위의 어떤 도시에서 사용되는 모든 언어를 지원해야 했다.

동맹에서 지원하는 언어가 많을수록 통역사의 일은 힘들어졌다. 훌륭한 통역사라면 그 모든 언어를 할 줄 알아야 했다! 다행히 많은 언어가 서로 비슷해서, 통역사가 이미 알고 있는 언어가 많을수록 새로운 언어를 배우기 쉬웠다. 새로 배우는 언어마다 통역사가 배우는 데 걸리는 시간은 절반씩 줄어들었다.

동맹의 언어 난이도란 통역사가 동맹에서 지원하는 모든 언어를 배우는 데 필요한 시간을 말한다. 첫 번째 언어를 배우는 데 2k 단위 시간이 걸리므로, 동맹의 언어 난이도는 2k + 2k−1 + . . . + 2k+1−t와 같다. 여기서 t는 동맹에서 지원하는 서로 다른 언어의 수이다. 전체 언어가 k개이므로 이 합은 항상 정수이다.

동맹 분할이란 모든 도시를 여러 동맹으로 나누는 분할을 말한다. 두 동맹 분할은, 한 분할에서는 같은 동맹에 속하지만 다른 분할에서는 서로 다른 동맹에 속하는 두 도시 u와 v가 존재하면 서로 다른 것으로 본다.

동맹 분할의 개연성이란 그 분할에 속한 모든 동맹의 언어 난이도의 합을 말한다.

가능한 모든 동맹 분할의 개연성의 합을 계산해야 한다. 이 값은 매우 클 수 있으므로 998 244 353으로 나눈 나머지만 구하면 된다.

첫 번째 줄에는 도시의 수 n과 언어의 수 k가 주어진다 (1 ≤ n ≤ 5000; 1 ≤ k ≤ 10).

두 번째 줄에는 n개의 정수 a1, a2, . . . , an이 주어진다. 이는 각 도시에서 사용하는 언어이다 (1 ≤ ai ≤ k).

다음 n − 1개 줄에는 각각 두 정수 ui와 vi가 주어진다. 이는 i번째 도로가 연결하는 두 도시이다 (1 ≤ ui, vi ≤ n).

가능한 모든 동맹 분할의 개연성의 합을 998 244 353으로 나눈 나머지를 출력한다.