시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

Bobo has a tree with $n$ vertices. There are $m$ vertices on the tree that bobo thinks very special.

bobo would like to choose a (maybe empty) subset of vertices as control points, so that every special vertex can reach an control points via no more than $r$ edges.

Find out the number of such subsets, modulo $(10^9 + 7)$.

입력

The first line contains $3$ integers $n, m, r$ ($1 \leq n \leq 2000, 0 \leq m \leq n, 0 \leq r < n$).

Vertices are numbered by $1, 2, \dots, n$ for convenience.

The second line contains $m$ distinct integers $v_1, v_2, \dots, v_m$ which denotes the special vertices ($1 \leq v_i \leq n$).

Each of the following $(n - 1)$ lines contains $2$ integers $a_i, b_i$ which denotes an edge between vertices $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$).

출력

A single integer denotes the number of subsets.

예제 입력 1

3 1 1
1
1 2
2 3

예제 출력 1

6

예제 입력 2

4 1 2
1
1 2
2 3
2 4

예제 출력 2

15