Expected Learning Time Calculation

ZHY, an aspiring rapper, is studying Migos' works. He has selected \( n \) tracks, indexed \( 1,2,\dots,n \). He learns them sequentially, spending 1 minute per attempt. For the \( i\)-th track, after 1 minute he either learns it successfully with probability \( P_i \) (and then moves on to track \( i+1 \), with track \( n+1 \) meaning the end) or fails with probability \( 1-P_i \). When he fails at track \( i \), his memory gets muddled: he only remembers the first \( x_i \) tracks and must restart at track \( x_i+1 \).

The twist is that the values \( x_i \) (for \( 1\le i\le n \)) are determined by \( m \) given pairs of natural numbers \((l_j, r_j)\) with \(0\le l_j<r_j\le n\). In particular, for each \( i \), \[ x_i = \max\{ l \mid \exists\,1\le j\le m, \; l=l_j \text{ with } l_j+1\le i\le r_j \}\] with the convention that if no such pair exists, then \( x_i = 0 \).

Thus, the expected additional minutes \( E(i) \) needed starting from track \( i \) satisfies for \( 1\le i\le n \): \[ E(i) = 1 + P_i\,E(i+1) + (1-P_i)\,E(x_i+1). \quad (\ast) \] Note that when \( x_i+1 = i \) (i.e. \( x_i = i-1 \)), the equation is self-referential. In that case, rearrange \((\ast)\) to obtain: \[ E(i) = \frac{1+P_i\,E(i+1)}{P_i}. \quad (\dagger) \]

You are given \( n \) tracks, \( m \) pairs \((l_j, r_j)\) that determine the \( x_i \)'s, and a sequence of initial probabilities \( P_i \) (given as integer percentages, so that the actual probability is \( P_i/100 \)). Then, you will receive \( k \) queries. Each query is one of the following two types:

• Type 1: 1 i p — update the learning success probability of track \( i \) to \( p/100 \).
• Type 2: 2 — answer the expected total number of minutes to finish learning all tracks, computed using the current probabilities and the equations above. Output the answer modulo \( 10^9+7 \).

You may assume that all operations lead to a finite expected time. Use modular arithmetic with modulus \( 10^9+7 \). In particular, when division is required, multiply by the modular inverse.

inputFormat

The first line contains three integers \( n, m, k \) — the number of tracks, the number of intervals, and the number of queries.

Each of the next \( m \) lines contains two integers \( l_j \) and \( r_j \) (with \(0\le l_j<r_j\le n\)).

The next line contains \( n \) integers \( p_1, p_2, \dots, p_n \) (each between 0 and 100), representing the initial percentages for \( P_1, P_2, \dots, P_n \) respectively.

Then follow \( k \) lines, each representing a query. A query is either of the form:

• 1 i p — update \( P_i \) to \( p/100 \), or
• 2 — output the current expected total minutes modulo \( 10^9+7 \).

outputFormat

For each query of type 2, output a single integer — the expected total number of minutes (modulo \( 10^9+7 \)).

sample

3 1 3
0 2
50 50 50
2
1 1 100
2

14
10