Time Limit: 10000 ms Memory Limit: 65536 KiB
There is an rooted weighted tree of n nodes. The root will be always 1. Let\'s define dist(u, v) as the distance from u to v.
Now you are been given the distance from the root to all other nodes. You need to count the number of different trees when all the edge weights are between [l, r]. Two trees A and B are different if and only if there exists an edge (u, v, w) in A but there is no such edge in B.
The first line contains a integer n(1 ≤ n ≤ 10^5), indicating the number of nodes in the tree. The second line contains n-1 integers start from dist(0, 1) to dist(0, n-1)(0 ≤ dist(0, i) ≤ 10^9). The next line contains a integer q(1 ≤ q ≤ 10), indicating the number of query you need to answer. The next q lines, each line contains two number l and r(1 ≤ l ≤ r ≤ 10^9) indicating a specific query.
For each query, output the answer in a single line. The number can be very huge, mod it with 10^9 + 7.
4 1 1 2 3 1 1 1 2 2 2
2 3 0