A Counting Problem solution codechef- Consider an array AA of length NN. You know that for all 1≤i≤N1≤i≤N, 0≤Ai≤1050≤Ai≤105. We construct an array BB of length N−1N−1 such that, for all 1≤i≤N−11≤i≤N−1, Bi=min(Ai,Ai+1)Bi=min(Ai,Ai+1).

A Counting Problem solution codechef

Consider an array AA of length NN. You know that for all 1iN1≤i≤N0Ai1050≤Ai≤105. We construct an array BB of length N1N−1 such that, for all 1iN11≤i≤N−1Bi=min(Ai,Ai+1)Bi=min(Ai,Ai+1).

You are given the array BB, you need to find out the total number of distinct arrays AA which we could have used to construct the given array BB.

The answer may be large, so you need to find it modulo 109+7109+7.

Input Format

  • First line will contain TT, number of testcases. Then the testcases follow.
  • The first line of each test case contains a single integer NN
  • The second line of each test case contains N1N−1 space separated integers – the ithith of which is BiBi

Output Format

For each testcase(in a new line), output the count of valid possibilities of array AA modulo 109+7109+7.

Constraints

  • 1T101≤T≤10
  • 2N1052≤N≤105
  • 0Bi1050≤Bi≤105

Sample Input 1 

3
2
100
5
3 9 8 4
3
10 12

Sample Output 1 

199801
199983
199977

Explanation

Test Case 11: All valid arrays AA are of the form [100,x][100,x] and [x,100][x,100] where 100x105100≤x≤105. Therefore, the answer is (105100)+(105100+1)=199801(105−100)+(105−100+1)=199801.

Test Case 33: All valid arrays AA are of the form [10,12,x][10,12,x] and [10,x,12][10,x,12] where 12x10512≤x≤105. Therefore, the answer is (10512)+(10512+1)=199977(105−12)+(105−12+1)=199977.

Leave a Comment