1756. Making Colors

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) .


标准输入 复制文本
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++.


2022 软件学院 ACM 集训队筛选赛 (热身赛)

单点时限 3 秒
内存限制 512 MB
提交 23
通过 13