A Journey to Rupsha

Tomorrow, April 14th, 2019 is a special day. Guess why.

Bengali New Year?

Your guess was partially correct. But there's another reason. Tomorrow, the season 8 of the epic fantasy TV series Game of Thrones will be premiered on HBO. This is the final season of the series.

For those, who don't know about the series, we won't give you any spoiler. So, you can assume that the problem statement is spoiler free.

Ramsay Bolton and Theon Greyjoy are best friends. They live in a small town named Teligati. The city is located at the center of the North.
One day they decided to visit the city Rupsha which is far south form the wall.

On their journey, they found some mysterious places. One of them is Fulbari Gate. To pass Fulbari Gate they need to break a chain which consists of some heavy locks. Breaking the chain is very tough. To do this, they need to perform some operations on the locks of the chain.

You are a free folk and they requested you to help them in this situation.

You are given the chain $A$ which contains $N$ locks.

You need to perform $Q$ queries of the following two types:

Multiply l r — multiply $3^0$ with $A_l$, $3^1$ with $A_{l + 1}$, $3^2$ with $A_{l + 2}$, …, $3^{r - l}$ with $A_r$.

Ask x — print the value of the lock $A_x$ with modulo $10^9+7$.

Input

The first line contains two integers $N$ and $Q$ ($1 ≤ N ≤ 10^5$, $1 ≤ Q ≤ 10^5$) — the number of elements in array A and the number of queries.

The second line contains n integers $a_1$, $a_2$, …, $a_n$ ($1 ≤ a_i ≤ 10^{18}$) — the locks of chain $A$.

Then q lines follow, describing queries in the format given in the statement.

Multiply l r ($1 ≤ l ≤ r ≤ n$) — denotes a multiplication query.

Ask x ($1 ≤ x ≤ n$) — denotes a query on the value of the lock of index $x$.

Output

For each Ask query, print the answer to it.

Sample

Input	Output
5 5 4 5 4 7 10 Multiply 1 5 Ask 1 Multiply 2 5 Ask 3 Ask 5	4 108 21870