 # finding k tuple

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

Have you tried the new option in the online explorer K-TuplesO74? I guess it’s the most appropriate to calculate the number in the tree. I tried that working on the section Academic Styles essaydune.com based.
In fact, K-TuplesO74 is available for free at github, but I bought a license on it not to tempt the fate.

//