sets-1

You are given a set S of N elements. You are supposed to form an array A such as:
S = {1,2,3}
then we have its subsets as {},{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}.
Then A consists of the largest  number(0 for empty set) from each subset.
A = {0,1,2,3,2,3,3,3}
Now the actual task comes here.
there are three types of queries such as :
m is an integer.
< m , no. of elements in A that are < m. 
> m , no. of elements in A that are > m.
= m , no. of elements in A that are = m.
Input
1st line consists of two space separated integers N and Q denoting the no. of elements in the given set and queries respectively. 1 ≤ N,Q ≤ 5*pow(10,5)
2nd line consists of N space separated integers, the elements of set S.Each element's value in the range (1,10^9)
Next Q lines follow each line denoting a type of query and integer m. 1 ≤ m ≤ pow(10,9);

Output
print the answer for each query in the output.
Note: the answer might be very large. So print modulo pow(10,9)+7

SAMPLE INPUT
3 5
1 2 3
> 3
= 2
= 3
> 1
< 1

SAMPLE OUTPUT
0
2
4
6
1

Source: hackerearth | Difficulty: MEDIUM


Solutions: