When Yunyan first arrived the Blue Planet through the Abyss portal, everything is a little blueish. The blue makes people blue. So Yunyan wanna make the planet more colorful. Also, the more colorful, the more powerful magic power would spring up in the Blue Planet. Luckily, he owns an Abyss machine which can make colors. So he'd like to use it to paint the planet.

There're three dimensions of an color, which are $R, G, B$ . They are real numbers and at first they are all $1$ . You can use $3$ basic transformations below:

1. Give $\dfrac13G$ and $\dfrac23B$ to $R$
2. Give $\dfrac13B$ and $\dfrac23R$ to $G$
3. Give $\dfrac13R$ and $\dfrac23G$ to $B$

For example, if origin $(R,G,B)$ is $(R_0,G_0,B_0)$ , then after transformation $1$ it becomes $(R_0+\dfrac13G_0+\dfrac23B_0,\dfrac23G_0,\dfrac13B_0)$ .

Now there's a transformation sequence $s$ of length $n$ . The i-th element $s_i$ denotes one kind of the three transformations.

There're $m$ queries. For each query. you need to perform some serial transformations in order $s_l, s_{l+1},\cdots, s_r$ from origin $(R,G,B)=(1,1,1)$ and figure out the final $(R,G,B)$ .

Suppose the answer value is an fraction $\dfrac xy$ , you should output $\dfrac xy\bmod (10^9+7)$ for every value.

Input the first line with two integers $n,m(1\le n,m\le10^5)$ .

Input the second line with $n$ integers, the i-th integer is $s_i(1\le s_i\le 3)$ .

Then input $m$ lines, each line with two integers $l,r(1\le l\le r\le n)$ , denoting an query.

Output $m$ lines, each line with three integers, denoting the final $(R,G,B)\bmod(10^9+7)$ .

For the first query, $(2,\dfrac23,\dfrac13)\bmod(10^9+7)=(2,666666672,333333336)$ .

For the fourth query, $(2\times\dfrac13,\dfrac23+\dfrac23\times 2+\dfrac13\times\dfrac13,\dfrac13\times\dfrac23)=(\dfrac23,\dfrac{19}9,\dfrac29)$ , and $(\dfrac23,\dfrac{19}9,\dfrac29)\bmod(10^9+7)=(666666672,111111114,222222224)$ .

You may use a fast way to input/output, such as scanf in C/C++.