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:
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) .
样例
| 标准输入 复制文本 |
5 6 1 2 3 1 1 1 1 2 2 3 3 1 2 3 4 1 5 |
| 标准输出 复制文本 |
2 666666672 333333336 333333336 2 666666672 666666672 333333336 2 666666672 111111114 222222224 111111114 222222224 666666672 814814823 794238689 390946505 |
提示
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++.