Jump Jump Expected Score

Little A plays a game called “Jump Jump” with the following rules:

1. Initialize a counter \(cnt=2\).
2. If he jumps to the next cell but misses its center, he gains 1 point and \(cnt\) is reset to 2.
3. If he jumps to the next cell and lands exactly in its center, he gains \(cnt\) points and then \(cnt\) is doubled.
4. If the next cell is a special cell \(x_i\) and he lands in its center, he receives an additional \(y_i\) bonus points.
5. The game ends if he fails to jump to the next cell or after all cells have been attempted.

There are (n) cells numbered from 1 to (n) (the starting cell is not counted). On each jump attempt there are three possible outcomes:

• Jump but miss the center with probability \(a\%\).
  Score: +1, and reset \(cnt\) to 2.
• Jump and hit the center with probability \(b\%\).
  Score: +\(cnt\) plus, if the current cell is special, the bonus \(y_i\) is also added; then update \(cnt\) to \(2\times cnt\).
• Fail to jump (i.e. do not jump) with probability \((100-a-b)\%\), which terminates the game immediately.

The process is performed cell by cell (maximum (n) moves). Calculate the expected total score and output the answer modulo (10^9+7).

Hint: Use dynamic programming with state (dp(i, c)) representing the expected additional score from cell (i) with the current counter value (c). You can show that the recurrence is linear in (c), i.e. you can write [ dp(i,c)=A[i]\cdot c+B[i], ] and derive recurrences for (A[i]) and (B[i]) from the probabilities. Remember to perform all computations modulo (10^9+7) and to handle probabilities (given as percentages) by multiplying with the modular inverse of 100.

Input note: Special cells yield extra bonus only when a center jump happens.

inputFormat

The first line contains four integers (n), (a), (b), and (m), where (n) is the total number of cells, (a) and (b) represent percentages, and (m) is the number of special cells. Each of the following (m) lines contains two integers (x) and (y), meaning that cell (x) is special with an extra bonus of (y) (if a cell is not special, its bonus is 0).

outputFormat

Output a single integer: the expected total score modulo (10^9+7).

sample

3 30 50 1
2 10

204000010