Expected Cells (Stretch)

This is a stretch problem.

There is an $n \times m$ grid of cells. Cell $(r, c)$ has a positive weight $w_{r, c}$. Let $W = \sum_{r, c} w_{r, c}$.

Two cells $A$ and $B$ are sampled independently, with replacement. The probability of choosing cell $(r, c)$ on a single sample is $w_{r, c} / W$.

Let $R$ be the smallest axis-aligned rectangle of grid cells that contains both sampled cells, and let $A$ be the number of cells inside $R$ (the area of $R$ counted in cells). If $A$ and $B$ are the same cell, then $R$ is that single cell and the area is $1$.

Output the expected value of $A$.

It can be shown that the answer can be expressed as a rational number $P/Q$ in lowest terms with $Q$ coprime to $10^9 + 7$. Output $P \cdot Q^{-1} \bmod (10^9 + 7)$.

Input

The first line contains two integers $n$ and $m$.

Each of the next $n$ lines contains $m$ integers. The $c$-th number on the $r$-th of these lines is $w_{r, c}$.

Rows and columns are indexed from $1$.

Output

Print a single integer: the expected number of cells in the bounding rectangle, modulo $10^9 + 7$.

Constraints

• $1 \le n, m$
• $n \cdot m \le 2 \cdot 10^5$
• $1 \le w_{r, c} \le 10^6$

Example 1

2 2
1 1
1 1

250000004

Explanation

All $16$ ordered pairs of cells are equally likely. The expected area is $9/4$, and $9 \cdot 4^{-1} \equiv 250000004 \pmod{10^9 + 7}$.

Example 2

1 1
5

1

Explanation

Both samples are the only cell, so the rectangle always has area $1$.

Example 3

1 3
1 1 1

888888897

Explanation

The expected area is $17/9$, and $17 \cdot 9^{-1} \equiv 888888897 \pmod{10^9 + 7}$.