Problem:
You have a Tree with
N
N nodes rooted at 1 where
i
t
h
ith node is associated with a value
A
i
Ai. Now consider the following definition:
K-Tuple: A tuple of
K+1 nodes
(
X
1
,
X
2
,
X
3
,
…
,
X
K
+
1
)
(X1,X2,X3,…,XK+1) is a K-Tuple if:
1.)
X
i
Xi is an ancestor of
X
i
+
1
∀
1
≤
i
≤
K
Xi+1∀1≤i≤K
2.)
A
X
i
A
X
i
+
1
∀
1
≤
i
≤
K
AXi>AXi+1∀1≤i≤K
Calculate the number of K-Tuples in the tree.
Input:
First line contains two integers
N
N and
K
K, the number of nodes in the tree and the value for the Tuple type you need to calculate answer for.
Next line contains
N
N space separated integers where the
i
t
h
ith integer denotes the value
A
i
Ai.
Next
N
−
1
N−1 lines contains
X
X and
Y
Y denoting that there is an edge between them.
Output:
Output a single integer mod
(
10
9
+
7
)
(109+7) denoting the number of K-tuples in the tree.
Constraints:
1
≤
N
,
A
i
≤
100000
1≤N,Ai≤100000
1
≤
X
,
Y
≤
N
1≤X,Y≤N
1
≤
K
≤
20
1≤K≤20
time limit - 2 sec
SAMPLE INPUT -
7 2
7 6 5 4 3 2 1
1 2
1 3
2 4
2 5
3 6
3 7
SAMPLE OUTPUT -
4