Description

$doby$ is an archer, and he really likes holding arrows.

One day, he came to an archery range and found that the owner had set up $n$ targets (numbered from $1-n$). Between them, $n-1$ lines were drawn so that the $n$ targets and the $n-1$ lines form a tree rooted at $1$. Each target has a score value.

To train himself, he chooses a node (called the parent node), then shoots once at every target in its subtree (including itself). Each target is hit with probability $50\%$. After finishing shooting a subtree, the total score he gets is the product of the scores of all targets that were hit.

Now he wants to know: if he chooses different nodes as the parent node, what is his expected total score? Since the total score may be very large, you need to take the result modulo $19260817$ (a prime).

Input Format

The first line contains two positive integers $n$ and $m$, the number of targets and the number of queries.

The next line contains $n$ positive integers, representing the scores of targets numbered $1-n$.

The next $n-1$ lines each contain two integers $u,v$, describing an undirected edge of the tree.

The next $m$ lines each contain one positive integer $x(1\leq x\leq n)$, meaning a query for the expected total score that $doby$ obtains when target $x$ is chosen as the parent node.

Output Format

Output one line with one positive integer $out$.

To reduce output, define $out$ as the sum of the expected total scores over all queries. Since this is an expectation, when computing $\frac{a}{b}$, you should compute it as $a*b^{-1} mod (19260817)$. You also need to take $out$ modulo $19260817$.

2 1
1 2
2 1
1

14445614

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

16251447

Hint

Note: Since the modulus is large, be careful about overflow of intermediate results when computing modular inverses.

If you do not need extreme optimization, using fast exponentiation to compute modular inverses is enough.

[Sample #$1$ Explanation]

The answer is $\frac{5}{4}$. The possible total scores are $0$, $1$, and $2$.

[Sample #$2$ Explanation]

The answers are $9630410$, $10834247$, and $15047607$, i.e. $\frac{3}{2}$, $\frac{599}{16}$, and $\frac{2999}{32}$.

$Subtask$ #$1$ ($10$ points):

$1\leq n,m\leq 10$.

$Subtask$ #$2$ ($40$ points):

$1\leq n,m\leq 100000$.

$Subtask$ #$3$ ($50$ points):

$1\leq n,m\leq 2000000$.

For all test points, the time limit is $1.5s$, and the memory limit is $125M$.

Problem setter: $1jia1$

Translated by ChatGPT 5