#574. 【ULR #1】多线程计算

样例一

input

1 1 1
0 0



output

499122177



样例二

input

2 2 1
1 1



output

798595483



explanation

$\rm O$ 表示亮灯, $-$ 表示未亮灯, 以下四种情况为节能态:

$\begin{bmatrix}\rm O&\rm O\\\rm O&-\end{bmatrix}$ $\begin{bmatrix}\rm O&-\\\rm O&\rm O\end{bmatrix}$ $\begin{bmatrix}-&\rm O\\\rm O&\rm O\end{bmatrix}$ $\begin{bmatrix}\rm O&\rm O\\-&\rm O\end{bmatrix}$

样例三

input

3 3 3
0 0
1 1
2 2



output

720162004



explanation

$\begin{bmatrix}\rm O&\rm O&-\\ \rm O&\rm O&\rm O\\-&\rm O&\rm O\end{bmatrix}$ 是一种满足数对 $(1,1)$ 的可能的节能态。

限制与约定

$1$ $10$ $10$ $n\times m$ $25$
$2$ $3000$ $500$ $1$ $10$
$3$ $n\times m$ $10$
$4$ $5\times 10^5$ $1$ $5$
$5$ $50$ $10$
$6$ $n\times m$ $20$
$7$ $5\times 10^5$ $20$