You’re given a tree with n vertices. How many ways there are to weight ith edge with one of the integers in interval [li,ri] such that sum of the weights of all paths does not exceed k. output the answer modulo 1e9+7.

1<=n,k<=1e5 1<=li<=ri<=1e5

Can anyone help me??