Today, Monk wants to handle Xor queries. He has to handle two types of queries:

1) Insert a number into the set. This query will be given in the form 1 x, where x is the number to be inserted.

2) Take all sub-sequences of the set and xor all elements of each sub-sequence together. Then, take all these values and find the number of distinct elements between them, modulo 10^9 + 7. This query will be given in the form 2. Note that the empty sub-sequence does count, and has a value of 0.

Note the sub-sequence does not have to be contiguous.

Input:

First line consists of Q, the number of queries.

Next Q lines consist of one integer T the type of query , if T is 1 then it's first type query and the same line have another integer x , if T is 2 then query of second type

Output:

For each query of type 2, output the answer.

Constraints:

1<=Q<=10^5

0<=x<=2*10^18