1407. Cocoa's homework

Syaro acted the role of the thief Lapin during Fleur du Lapin opening hours. But unfortunately, dueto her lack of acting skills, all the attention was drawn away by other characters. So she made an appointment with Coco, Chino, Rize and Chiya to watch the Lapin TV series in the Rabbit House together at night. Syaro is watching TV while learning the movements of the thief Lapin

After watching the TV series, Rize, Chiya and Syaro left. Cocoa and Chino watched them leave atthe door of Rabbit House

When returning to Chino’s room, Cocoa suddenly remembered:

”I forgot to do my homework. Lapin stole my time!”

Cocoa’s teacher gave two arrays ofnnumbers A=[a1,a2,a3,...,an],B=[b1,b2,b3,...,bn]A= [a_1, a_2, a_3, ..., a_n], B= [b_1, b_2, b_3, ..., b_n] Then lether use these numbers and a number ww to form a n×nn×n matrix MM (index started from 11):

And let her find the determinant det(M)det(M) of this matrix MM.

Cocoa’s inspiration flashed, relying on her math skills, quickly calculated det(M)det(M). But Chino con-sidered that Cocoa looks silly , she must be wrong. Because Cocoa always does Chino a disservice when Rabbit House is open, and Chino always helps her clean up the mess. She changed several numbers in the array AA and BB, and gave ww arbitrarily, and let Cocoa do the calculation again to seeif it was right. Can you help Chino calculate the value of det(M)det(M) so that she can quickly help Cocoa check whether it is correct? And Cocoa also wants to finish her homework and go to bed as soon as possible.

输入

The first line is two integers n,Q (2n,Q100000)n, Q \ (2≤n, Q≤100000) . QQ means there are QQ operations. The nn integers in the second line represent the array AA, where each integer aia_i satisfies ai109|a_i|≤10^9.The nn integers in the third line represent the array BB, where each integer bib_i satisfies bi109|b_i|≤10^9 .In the next QQ line, there are three input types, representing three operations:

  • 1p x It means that the number in the array AA whose index is pp is changed to an integer xx, 1pn,x1091≤p≤n,|x|≤10^9.
  • 2 p x It means that the number in the array BB whose index is pp is changed to an integer xx, 1pn,x1091≤p≤n,|x|≤10^9.
  • 3 w Represents the given integer w,w109w,|w|≤10^9.

输出

For each operation 33, output the value of det(M)det(M). Since the value of det(M)det(M) is too large, please output it after modulo 109+710^9+ 7

样例

标准输入 复制文本
2 4
2 3
1 5
3 -1
1 2 4
2 1 6
3 1
标准输出 复制文本
12
999999972

提示

来源

SCNUCPC 2020 现场赛

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 3
通过 2