access_globe is recently playing a city planning game. In the game, there are $n$ cities and $n-1$ bidirectional roads connecting these cities, such that any two cities can reach each other through these roads.
Recently, the "World Cup" tournament has begun in the game. Each city supports exactly one team; let $a_i$ be the team supported by the $i$-th city. The game gives access_globe a new task: select some cities to build football stadiums that can host World Cup matches.
access_globe does not want the diversity of the teams supported by the cities with stadiums to be too high. Therefore, he requires that among the cities where stadiums are built, there cannot exist $3$ cities such that they all support different teams. At the same time, to reduce the time players spend on the road, access_globe wants any two cities with stadiums to be reachable from each other by passing only through other cities that also have stadiums.
access_globe is a person who likes variety, so he wants you to help him calculate how many different ways there are to build the stadiums. Two schemes are considered different if and only if there exists a city that has a stadium in exactly one of the schemes.
However, you do not want to solve this problem for him; you only want to tell him the answer modulo $998244353$.
Input
The first line contains an integer $n$, representing the number of cities.
The second line contains $n$ space-separated integers $a_1, \dots, a_n$, representing the team supported by each city.
The next $n-1$ lines each contain two space-separated integers $x_i, y_i$, representing a bidirectional road connecting city $x_i$ and city $y_i$. It is guaranteed that any two cities can reach each other through these roads.
Output
Output a single integer representing the number of different schemes to build stadiums modulo $998244353$.
Examples
Input 1
6
5 1 1 3 2 6
1 2
2 3
3 4
3 5
2 6Output 1
15Note 1
The road network and the teams supported by the cities are shown in the figure below, where cities of the same color support the same team.
The road network and team support distribution.
Any scheme with only one stadium or with stadiums built in two directly connected cities is valid, resulting in $5+6=11$ schemes. The remaining schemes involve building stadiums in cities $2$, $3$, and any other city, totaling $4$ schemes, for a total of $15$ schemes.
Subtasks
| Test Case | Score | $n=$ | Special Property |
|---|---|---|---|
| $1$ | $3$ | $500$ | None |
| $2$ | $7$ | $5,000$ | None |
| $3$ | $9$ | $2\times 10^5$ | A |
| $4$ | $13$ | $5\times 10^5$ | A |
| $5$ | $7$ | $2\times 10^5$ | B |
| $6$ | $11$ | $5\times 10^5$ | B |
| $7$ | $12$ | $5\times 10^4$ | None |
| $8$ | $14$ | $2\times 10^5$ | None |
| $9$ | $12$ | $5\times 10^5$ | None |
| $10$ | $12$ | $5\times 10^5$ | None |
For all data, it is guaranteed that $1\le a_i\le n\le 500000$. Hack data in QOJ is not restricted by the equality constraints in the table.
After submitting your code, your solution will be evaluated against pretest data and the results will be returned. This problem's pretest data consists of $10$ test cases, each with the same data scale constraints as the corresponding final test case.
Note: The evaluation results of the pretest data have no relation to the final evaluation results.
Note
Please note that the memory limit for this problem is 2 GB. Please calculate your program's memory usage carefully and do not exceed the limit. Exceeding the memory limit may result in a score of 0 points for the entire problem.