Background

JSOI is a kingdom with a highly developed transportation network. Recently, to prevent sabotage by enemy spies, King JS has ordered the Minister of Transportation, JYY, to inspect the resilience of an underground tunnel system.

Description

The underground tunnel system of JSOI consists of $R$ rows and $C$ columns of key nodes. The rows and columns are numbered from $0$ to $R-1$ and $0$ to $C-1$, respectively. The key nodes in the leftmost column (column $0$) and the rightmost column (column $C-1$) are the surface entrances and exits of the tunnel system. The tunnel system is connected by horizontal and vertical unit-length tunnels, forming a grid graph. The figure below shows a $3 \times 4$ underground tunnel system.

Based on precise estimates from the intelligence department, each underground tunnel has a probability $p$ of being destroyed. The destruction of each tunnel is an independent event.

Given this underground network, JYY needs to calculate the probability that the tunnel system remains operational after enemy sabotage. The tunnel system is operational if and only if there exists a path of non-destroyed tunnels that allows travel from any surface entrance in column $0$ to any surface exit in column $C-1$.

Input

The first line contains two integers $R$ and $C$.

The next $R$ lines each contain $C-1$ integers. The $j$-th integer in the $i$-th line represents the probability (as a percentage) that the tunnel to the right of node $(i-1, j-1)$ is destroyed.

The next $R-1$ lines each contain $C-2$ integers. The $j$-th integer in the $i$-th line represents the probability (as a percentage) that the tunnel below node $(i-1, j)$ is destroyed.

Output

Output a single integer representing the probability that all key nodes remain connected. To avoid complex floating-point operations, assume the simplest fractional representation of the final answer is $\frac{p}{q}$. You only need to output the value of $(p \cdot q^{-1}) \pmod{10^9 + 7}$. Here, $q^{-1}$ is the smallest positive integer such that $(q \cdot q^{-1}) \pmod{10^9 + 7} = 1$.

Examples

Input 1

2 3
50 50
50 50
50

Output 1

500000004

Input 2

6 7
73 18 90 15 56 70
88 37 19 1 65 62
83 77 75 48 48 50
31 76 91 25 34 45
65 9 60 9 38 46
51 74 92 67 74 48
81 60 93 38 97
35 38 95 93 52
6 73 96 18 92
11 79 31 34 56
27 70 5 44 13

Output 2

701609622

Constraints

For $30\%$ of the data, $R, C \le 4$. For $50\%$ of the data, $R \le 8$. For $100\%$ of the data, $1 \le R \times C < 110$, $1 \le p \le 99$.