Tree

Time Limit: 10000 ms Memory Limit: 65536 KiB

Problem Description

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.
 

Input

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.
 

Output

For each query, output the answer in a single line. The number can be very huge, mod it with 10^9 + 7.
 

Sample Input

4
1 1 2
3
1 1
1 2
2 2

Sample Output

2
3
0

Hint

 

Source

2014年山东省第五届ACM大学生程序设计竞赛