Random Subinterval Maximum Operations

You are given two arrays \(a\) and \(b\) of length \(n\). Initially you hold a number \(x=0\). When you step to position \(i\) (\(1 \le i \le n\)), you can update your number \(x\) to either \(x + a_i\) or \(x \times b_i\) (i.e. you choose one of the two operations).

You need to process \(m\) operations. There are two types of operations:

1. Update Operation: 1 x y z which sets \(a_x \gets y\) and \(b_x \gets z\).
2. Query Operation: 2 l r which asks: Consider the interval \([l, r]\). Among all of its contiguous subintervals \([l', r']\) (where \(l \le l' \le r' \le r\)), you choose one uniformly at random. For a fixed subinterval \([l', r']\), you start at the beginning with \(x=0\) and move from index \(l'\) to \(r'\); at each index \(i\) you may update your number to \(x + a_i\) or \(x \times b_i\) (and you want to maximize the final value). Let \(f(l', r')\) denote the maximum final value you can obtain on that subinterval. The answer to the query is the expected value of \(f(l', r')\) over all subintervals of \([l, r]\), taken modulo \(10^9+7\).</p>

   Note: Before processing each subinterval the initial number is always 0. If you are not familiar with taking the modulus of a rational number, you may refer to the problem P2613 Rational Numbers modulo.

   The formula for the DP on a chosen subinterval \([L, R]\) is as follows:

   [ \begin{aligned} x_{L} &= \max(0+a_{L},;0\times b_{L}) = \max(a_{L},0),\ x_i &= \max(x_{i-1} + a_i,; x_{i-1} \times b_i) \quad \text{for } i=L+1,\dots,R. \end{aligned} ]

   Your task is to process all \(m\) operations in order. For each query operation, compute and output the answer modulo \(10^9+7\). To obtain the answer for a query, sum \(f(l', r')\) for every contiguous subinterval \([l', r']\) of \([l, r]\) and then multiply by the modular inverse of the number of subintervals.

   inputFormat

   The first line contains two integers \(n\) and \(m\) — the size of the arrays and the number of operations.

   The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\).

   The third line contains \(n\) integers: \(b_1, b_2, \dots, b_n\).

   The following \(m\) lines each describe an operation in one of the following two formats:

   • 1 x y z — Update operation: set \(a_x\) to \(y\) and \(b_x\) to \(z\).
   • 2 l r — Query operation as described above.

   outputFormat

   For each query operation (i.e. operations of type 2), output one line containing the answer (the expected maximum final value modulo \(10^9+7\)).

   sample

   3 4
   1 2 3
   2 2 2
   2 1 3
   1 2 5 3
   2 1 2
   2 2 3

   333333339
   4
   6

   </p>