Random Rudreshwar  Problem code: ANURRZ

MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian as well.

Problem description

Rudreshwar likes random numbers and random arrays. Today Rudreshwar started playing with a couple of Arrays A and B, each of size N.

Initially A is filled with zeros. Rudreshwar filled B with random numbers.

Rudreshwar visits each index i (1 <= i <= N) in random order. When at i, he selects another random index jsuch that j is greater or equal to i. He then increments A[i], A[i+1], A[i+2] ... A[j] by 1.

Finally if for any index i, A[i] is greater than B[i], he then throws away that array A

For a given B, calculate the number of different arrays A, that Rudreshwar can end up with. Two arrays are called different if there exists an index where the arrays have different values

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. First line of each test case contains an integer N. Second line contains N space separated integers representing the array B

Output

For each test case, output a single line containing the required answer modulo 1000000007.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 1000
• 1 ≤ B[i] ≤ N

Example

Input:
2
2
2 2
3
1 1 1

Output:
2
1

Explanation

Test case 1

{1, 1} and {1, 2} are valid.

Test case 2

{1, 1, 1} is the only possible final array A.

Explanation

Here the DP state is quite unusual. First let us go with few observations

(1)   The maximum value of any index b[i] can be equal to i and not more.

(2)  The dp state is dp[i][j] which denotes that index i is chosen to be updated j times by indices before(including) it.

Standard explanation

In such kind of problems first thinking should be dynamic programming. Let's try to find answer for first i indexes. Can we relate the answer for i directly to answer for i-1. No! We need some additional information. Why don't we keep two states i and j denoting the number of different arrays of size i that can formed and number j is present at i'th position in such arrays. Basically dp(i, j) denotes number of arrays of size i such that j intervals end at i'th position. Note that for j > B_i, dp[i][j] would be zero, because it's not a valid array. Our answer will be dp(N, 1) + dp(N, 2) + ... + dp(N, B_N)

Now, let's try to form recurrences. What we should be thinking is for dp(i, j) which all are valid x such that dp(i-1, x)can be added to dp(i, j) ie. what valid numbers can come at position i-1 if j is present at index i?

Now, an interesting observation is that x can be any value greater than equal to j-1. It can be thought as: suppose xintervals were ending a index i-1, then we can choose to extend any number of them to index i to get any sum between 1 and x + 1(note that one interval starts and ends at i). So, we get that x can be any number greater than or equal to j-1.

So, here is our recurrence:

dp(i, j) = dp(i-1, N) + dp(i-1, N-1) + dp(i-1, N-2) ... dp(i-1, j-1)

So, if we calculate each state dp(i, j) in O(N), our total complexity will be O(N³).
But we can notice that dp(i, j) depends on a continuous sum in one dimensional array of dp(i-1).
So, if we calculate prefix sum array:
prefix[j] stores the sum dp(i-1, j) + dp(i-1, j+1) ... dp(i-1, N). So, prefix[j] = prefix[j+1] + dp[i-1][j]. We can calculate this prefix sum array in O(N).

Code

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int dp[1010][1010];

int pre[1010];

int b[1010]; 

#define mod 1000000007

int main()

{

 int t;

 cin>>t;

 while(t--)

 {

  int n;

  cin>>n;

    memset(dp,0,sizeof(dp));

    for(int i=1;i<=n;i++)

    scanf("%d",&b[i]);

    for(int i=1;i<=n;i++)

    b[i]=min(b[i],i);

    dp[1][1]=1;

    pre[0]=0;

    memset(pre,0,sizeof(pre));

    for(int i=1;i<=n;i++)

    {

            pre[i]+=dp[1][i];

  pre[i]+=pre[i-1];

  }

    for(int i=2;i<=n;i++)

    {

          for(int j=1;j<=b[i];j++)

  {

        int lf=max(j-1,1);

int rt=n;

dp[i][j]=(pre[n]-pre[lf-1]+mod)%mod;

  }

  for(int kk=1;kk<=n;kk++)

  {

        pre[kk]=0;

pre[kk]+=pre[kk-1];

   if(pre[kk]>=mod)

   pre[kk]%=mod;

 

pre[kk]+=dp[i][kk];

if(pre[kk]>=mod)

   pre[kk]%=mod;

  }

  }

 int ans=0;

  for(int i=1;i<=b[n];i++)

  {

    ans=(ans+dp[n][i]);

    if(ans>=mod)

    ans%=mod;

  }

  printf("%d\n",ans);

 }

 return 0;

}