You are given a tree with **A** nodes. You are given two integer array **B** and **C** which represents an edge i.e.

there is an edge from node **B[i]** to **C[i]**.You need to tell the count of subtrees such that the length of the longest path in the subtree is at most **D**.

Since this count may be very large. Return the count of such subtree modulo (10^{9}+7).

**Input Format**

```
The first argument is an integer A.
The second argument is an array of integers B.
The Third argument is an array of integers C.
The Fourth argument is an integer D.
```

**Output Format**

```
Return the count of subtrees such that the length of the longest path in the subtree is at most D modulo (10^9+7).
```

**Constraints**

```
2 <= A <= 60
1 <= B[i] , C[i] <= A
B[i]!=C[i]
1 <= D < A
```

**For Example**

```
Input 1:
A = 3
B = [1, 2]
C = [2, 3]
D = 1
2
/ \
1 3
Output 1:
5
subtrees with atmost longest path equal to 1 : 1, 2, 3, (1,2) , (2,3)
Input 2:
A = 6
B = [1, 2, 3, 3, 4]
C = [2, 3, 4, 5, 6]
D = 3
Output 2:
23
```

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

Sign Up

to access hints and editorial solutions for**Longest path in a subtree**

to access hints and editorial solutions for

Loading...