# Question Name:Xsquare And Number List

``````#include<bits/stdc++.h>

using namespace std;

#define i64 long long
#define MOD 1000000007

i64 bigMod(i64 n){

if(n == 0)
return 1;
if(n&1)
return (2*bigMod(n-1))%MOD;
i64 x = bigMod(n/2);
return (x*x)%MOD;
}

int main(){

i64 n, q, tmp, k;
char ch;
vector<i64> v;
scanf("%lld%lld", &n, &q);
for(int i = 0; i < n; i++){

scanf("%lld", &tmp);
v.push_back(tmp);
}
sort(v.begin(), v.end());
for(int i = 0; i < q; i++){
getchar();
scanf("%c%lld", &ch, &k);
if(ch == '<'){
i64 x = lower_bound(v.begin(), v.end(), k)-v.begin();
printf("%lld\n", bigMod(x));

}
else if(ch == '>'){

i64 x = upper_bound(v.begin(), v.end(), k)-v.begin();
printf("%lld\n", (bigMod(n)-bigMod(x)+MOD)%MOD);
}
else{

i64 x = upper_bound(v.begin(), v.end(), k)-v.begin();
i64 y = lower_bound(v.begin(), v.end(), k)-v.begin();
printf("%lld\n", (bigMod(x)-bigMod(y)+MOD)%MOD);
}
}
return 0;
}``````
• Problem Description
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.

For example :

Consider the following multi set consisting of 3 elements S = {1,2,3}.
List of all subsets:
1. { } or , the empty set, sometimes called the “null” set.
2. {1}
3. {2}
4. {3}
5. {1,2}
6. {1,3}
7. {2,3}
8. {1,2,3}

Final List:
{0}
{1}
{2}
{3}
{2}
{3}
{3}
{3}

Now, Xsquare wonders that given an integer K how many elements in the final list are greater than ( > ) , less than ( < ) or equals to ( == ) K.

To 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.

> K : Count the number of elements X in the final list such that X > K.
< K : Count the number of elements X in the final list such that X < K.
= K : Count the number of elements X in the final list such that X == K.
Note:

Answer to a particular query can be very large. Therefore, Print the required answer modulo 109+7.
An empty subset is replaced by an integer 0.
Input

First 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.

Output

For each query, print the required answer modulo 109+7.

Constraints:

1 N,Q 5*10^5
1 K,Si 10^9
query_type = { < , > , = }
Warning :

Prefer to use printf / scanf instead of cin / cout.
• Test Case 1
Input (stdin)3 5
1 2 3
< 1
> 1
= 3
= 2
> 3
Expected Output1
6
4
2
0
• Test Case 2
Input (stdin)2 5
2 4
< 1
> 1
= 3
= 2
> 3
Expected Output1
3
0
1
2  