QUESTION

Xsquare loves to play with numbers a lot. Today, he has a multi set S consisting of N integer elements. At first, he has listed all the subsets of his multi set S and later replaced all the subsets with the maximum element present in the respective subset.\nFor example :\nConsider the following multi set consisting of 3 elements S = {1,2,3}. \nList of all subsets:\n{}\n{1}\n{2}\n{3}\n{1,2}\n{2,3}\n{1,3}\n{1,2,3}\nFinal List:\n{0}\n{1}\n{2}\n{3}\n{2}\n{3}\n{3}\n{3}\nNow, Xsquare wonders that given an integer K how many elements in the final list are greater than ( > ) , less than ( < ) or equals to ( == ) K.\nTo make this problem a bit more interesting, Xsquare decided to add Q queries to this problem. Each of the queries has one of the following type.\n > K : Count the number of elements X in the final list such that X > K.\n < K : Count the number of elements X in the final list such that X < K.\n = K : Count the number of elements X in the final list such that X == K.\nNote:\n Answer to a particular query can be very large. Therefore, Print the required answer modulo 109+7.\n An empty subset is replaced by an integer 0.\nInput\nFirst line of input contains two space separated integers N and Q denoting the size of multiset S and number of queries respectively. Next line of input contains N space separated integers denoting elements of multi set S. Next Q lines of input contains Q queries each having one of the mentioned types.\nOutput\nFor each query, print the required answer modulo 109+7.\n.

“TESTCASE_1”: “3 5\n1 2 3\n< 1\n> 1\n= 3\n= 2\n> 3\n###—###SEPERATOR—###—\n1\n6\n4\n2\n0”, “TESTCASE_2”: “3 5\n2 3 4\n< 2\n> 3\n= 1\n= 2\n> 2\n###—###SEPERATOR—###—\n1\n4\n0\n1\n6”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
 
ll power(ll a,ll b)
{
     ll res=1;
     while(b)
     {
         if(b&1)
             res=(res*a)%mod;
         a=(a*a)%mod;
         b/=2;
     }
     return res;
}
int main()
{
     ll n,q,i,ans,ans1;
     scanf("%lld%lld",&n,&q);
     ll arr[n];
     for(i=0;i<n;i++)
        scanf("%lld",&arr[i]);
     ll x,l,r;
     char ch;
     sort(arr,arr+n);
     while(q--)
     {
         cin>>ch;
         scanf("%lld",&x);
        // cout<<ch;
         if(ch=='=')
         {
             r=upper_bound(arr,arr+n,x)-arr;
             ans1=(power(2,n)-power(2,r)+mod+mod)%mod;
             x--;
             l=upper_bound(arr,arr+n,x)-arr;
             ans=power(2,l);
             ans=(power(2,n)-ans-ans1+mod+mod)%mod;
            // cout<<l<<" "<<r<<" "<<(r-l+1)<<endl;
             //ans=power(2,r-l+1);
         }
         else if(ch=='<')
         {
             x--;
             r=upper_bound(arr,arr+n,x)-arr;
             ans=(power(2,r)+mod)%mod;
            // cout<<r<<endl;
         }
         else
         {
             r=upper_bound(arr,arr+n,x)-arr;
             ans=(power(2,n)-power(2,r)+mod+mod)%mod;
             //cout<<r<<endl;
         }
         ans=(ans+mod)%mod;
         printf("%lld\n",ans);
     }
}