Ddakji Problem Code: REC20C Answer

 » RECode 20.0 » Ddakji

Ddakji

Problem Code: REC20C

Add problem to Todo list

Submit

The Salesman is playing Ddakji with Seong Gi-Hun.

There are N cardboards kept at distinct positions, the ith of which can be flipped Ai times only. Gi-Hun gets 100 won with each flip. He has to play the game Q times and can select a series of consecutive positions to flip the cardboard kept at those positions .

The Salesman being clever, has already decided the series of positions, which Gi-Hun would have to select in all the games.

Since Gi-Hun is in huge debts, he should now stealthily arrange the cardboards in a manner so as to receive the maximum total sum of money.

Before actually arranging the cardboards, you must help him find the total number of distinct arrangements possible to obtain the maximum sum. Since the value can be large, find its modulo 109+7.

Note: Gi-Hun would only select the indices that The Salesman has already decided, even if their values are not the same as before.

Two arrangements are considered different if there exists at least one position where their values are not the same in both the arrangements.

Input Format

The first line contains T - the number of test cases. T testcases follow

The next line contains N - the number of cardboards

The next line contains N space separated integers - the number of possible flips of the ith cardboard.

The next line contains Q - the number of times Gi-Hun plays. Q lines follow.

Each of the Q lines contains two space separated integers- L,R- the series of indices from L to R(both inclusive), which Gi-Hun would have to select in the respective turn.

Output Format

Output a single integer for every testcase in a separate line- the number of ways to arrange the cardboards so as to receive the max total sum of money

Constraints

1≤T≤105

1≤N≤105

1≤Ai≤109

1≤Q≤105

1≤L,R≤N

The sum of N,Q over all testcases does not exceed 105

Sample Input 1 

1

5

3 5 7 2 1

3

1 2

3 5

2 4    

Sample Output 1 

12

Explanation

It can be proved that only 12 optimal arrangements of the given cardboards are possible

 

Click Here For Answer