시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB999100.000%

문제

Fytelandian scientists are famous for their love for historical research. Recently they have discovered the remains of n cities, which definitely belonged to a great past civilization.

All the discovered cities were connected by exactly n − 1 roads, and there was exactly one way to move between any pair of cities using these roads. The scientists found a lot of writings in each city and concluded that people of the civilization spoke k different languages. In city v people spoke language av.

It is known that the cities formed several alliances, and each city belonged to exactly one alliance. However, the exact formation of alliances remains unknown.

Let’s say that an alliance is an arbitrary set of cities c1, c2, . . . , cm that might or might not be connected by roads. To rule the alliance it was necessary to be able to make connections between different cities with people who speak different languages. The head of the alliance had to support all languages that were spoken either in some city ci of the alliance or in some city on the shortest path between some two cities ci and cj of the alliance.

The more languages were supported in the alliance, the harder was the translator’s job — a good translator had to speak all of them! Luckily, many languages were similar to each other, and the more languages the translator had known, the easier it was for them to learn a new language. Every consecutive new language took twice less time for the translator to learn.

Let’s say that the language difficulty of the alliance is the time the translator needed to spend to learn all languages supported in the alliance. The first language took 2 k units of time to learn, thus, the language difficulty of the alliance is equal to 2k + 2k−1 + . . . + 2k+1−t, where t is the number of different languages supported in the alliance. Note that as there are k languages in total, this sum is always an integer.

Let’s say that an alliance partition is a partition of all cities into several alliances. Two alliance partitions are considered different if there exist two cities u and v such that they belong to the same alliance in one partition and to different alliances in the other partition.

Let’s say that the plausibility of an alliance partition is the sum of the language difficulties of all alliances in the partition.

You need to calculate the sum of the plausibilities of all possible alliance partitions. As this number can be very big, you need to find only its remainder modulo 998 244 353.

입력

The first line of the input contains two integers n and k — the number of cities and the number of languages, respectively (1 ≤ n ≤ 5000; 1 ≤ k ≤ 10).

The second line contains n integers a1, a2, . . . , an — the languages spoken in the cities (1 ≤ ai ≤ k).

Each of the following n − 1 lines contains two integers ui and vi — cities connected by the i-th road (1 ≤ ui, vi ≤ n).

출력

Output the sum of the plausibilities of all possible alliance partitions modulo 998 244 353.

예제 입력 1

3 2
1 2 1
1 2
2 3

예제 출력 1

48

In the first example, there are three cities. Consider all possible alliance partitions:

  • Three alliances: The plausibility of this partition is 4 + 4 + 4 = 12.
    • {1}. One city, the only supported language is language 1. The language difficulty is 22 = 4.
    • {2}. One city, the only supported language is language 2. The language difficulty is 22 = 4.
    • {3}. One city, the only supported language is language 1. The language difficulty is 22 = 4.
    The plausibility of this partition is 4 + 4 + 4 = 12.
  • Two alliances:
    • {1, 2}. Two cities, languages 1 and 2 are supported. The language difficulty is 22 + 21 = 6.
    • {3}. One city, the only supported language is language 1. The language difficulty is 22 = 4.
    The plausibility of this partition is 6 + 4 = 10.
  • Two alliances:
    • {1, 3}. Two cities, languages 1 and 2 are supported. Note that even though the only language spoken in the alliance is language 1, language 2 is supported as well because it’s spoken in city 2 that lies on the shortest path between cities 1 and 3. The language difficulty is 22 + 21 = 6.
    • {2}. One city, the only supported language is language 2. The language difficulty is 22 = 4.
    The plausibility of this partition is 6 + 4 = 10.
  • Two alliances:
    • {1}. One city, the only supported language is language 1. The language difficulty is 22 = 4.
    • {2, 3}. Two cities, languages 1 and 2 are supported. The language difficulty is 22 + 21 = 6.
    The plausibility of this partition is 4 + 6 = 10.
  • One alliance:
    • {1, 2, 3}. Three cities, languages 1 and 2 are supported. The language difficulty is 22 + 21 = 6.
    The plausibility of this partition is 6.

The required sum is equal to 12 + 10 + 10 + 10 + 6 = 48.

예제 입력 2

6 4
1 2 1 3 4 2
1 2
2 3
3 5
3 4
2 6

예제 출력 2

14504