Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A Journey to Rupsha

Limits: 1s, 512 MB

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 30 with Al, 31 with Al + 1, 32 with Al + 2 , ……. , 3(r - l) with Ar.

Ask x — print the value of the lock Ax with modulo 109+7.

Input

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

The second line contains n integers a1,a2,…,an (1 ≤ ai ≤ 1018) — 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.

Samples

InputOutput
5 5
4 5 4 7 10
Multiply 1 5
Ask 1
Multiply 2 5
Ask 3
Ask 5
4
108
21870

For your information,

Theon Greyjoy and Ramsay Bolton

Discussion