**1085 - All Possible Increasing Subsequences( of any length)

                                1085 - All Possible Increasing Subsequences


An increasing subsequence from a sequence A1, A2 ... An is defined by Ai1, Ai2 ... Aik, where the following properties hold

1.      i1 < i2 < i3 < ... < ik and
2.      Ai1 < Ai2 < Ai3 < ... < Aik

Now you are given a sequence, you have to find the number of all possible increasing subsequences.

Input
Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 105) denoting the number of elements in the initial sequence. The next line will contain n integers separated by spaces, denoting the elements of the sequence. Each of these integers will be fit into a 32 bit signed integer.

Output
For each case of input, print the case number and the number of possible increasing subsequences modulo 1000000007.

Sample Input
Output for Sample Input
3
3
1 1 2
5
1 2 1000 1000 1001
3
1 10 11
Case 1: 5
Case 2: 23
Case 3: 7
Notes
1.      For the first case, the increasing subsequences are (1), (1, 2), (1), (1, 2), 2.
2.      Dataset is huge, use faster I/O methods.

----------------------------------------EDITORIAL---------------------------------------------------------------
THIS PROBLEM CAN BE EASILY SOLVED  USING SEG TREE ,  FIRST OF ALL SORT ALL THE ELEMENTS WITH THERE INDEX , SINCE ANY NUMBER  CAN BE PLACED AFTER ANY NUMBER LESS THAN THAT NUMBER AND COMES BEFORE THAT NUMBER.....

AFTER SORTING  NOW WE PROCESS EACH ELEMENT ONE BY ONE , AND  FOR ANY NUMBER IT CAN BE PLACED  AFTER ALL NUMBER PROCESSED TILL NOW AND HAVE INDEX LESS THAN INDEX OF THIS NUMBER ,
SO BASICALLY WE CAN PLACE THIS NUMBER AFTER ALL POSSIBLE SEQUENCE TILL IDX-1 ,
SO IT IS THE SUM FROM  0 TO IDX-1,

AND ALSO UPDATE THIS SUM AT IDX

-----------------------------------------------CODE------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef  int lli;
vector<pair<lli,int> > v;
lli arr[1000000];
lli seg[1000000];

#define mod 1000000007
void  update(int idx,int start,int end,int ups,int upe,int val)
 {
   if(start>end  ||upe<start || ups>end)
    {
      return ;
   }
   else if(start==end  && start==ups)
    {
      seg[idx]=(seg[idx]+val)%mod;
      return ;
}
int mid=(start+end)/2;
update(2*idx,start,mid,ups,upe,val);
update(2*idx+1,mid+1,end,ups ,upe,val);
seg[idx]=(seg[2*idx]+seg[2*idx+1])%mod;

 }

 lli qry(int idx,int start,int end,int ups,int upe)
  {
   if(start>end || upe<start || ups>end)
    {
      return 0 ;
   }
   else if(start>=ups && end<=upe)
    {
  
      return seg[idx] ;
}
int mid=(start+end)/2;
lli q1= qry(2*idx,start,mid,ups,upe);
lli q2= qry(2*idx+1,mid+1,end,ups ,upe);
return (q1+q2)%mod;
  }
  bool comp(pair<int,int> p1,pair<int,int> p2)
   {
     if(p1.first<p2.first) return true;
     else if(p1.first==p2.first && p1.second>p2.second) return true;
     else return false;
   }
int main()
{
int t;
 cin>>t;
 int cas=1;
 while(t--)
 {
 
  memset(seg,0,sizeof seg);
  int n;
  v.clear();
   cin>>n;
   for(int i=1;i<=n;i++)
    {
       int a;
        scanf("%d",&a);
        v.push_back({a,i});
   }
   sort(v.begin(),v.end(),comp);
    update(1,0,n,0,0,1);
   for(int i=0;i<n;i++)
    {
      int num=v[i].first;
      int idx=v[i].second;
      int count=qry(1,0,n,0,idx-1);
      update(1,0,n,idx,idx,count);
    
}
lli ans=qry(1,0,n-1,1,n);
printf("Case %d: %lld\n",cas++,ans);
 }
}