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.

Answer 1

Consider the following multi set consisting of 3 elements S = {1,2,3}.

List of all subsets:

{}

{1}

{2}

{3}

{1,2}

{2.3}

{1,3}

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

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.