AGC022E Median Replace

给出一个长度为奇数 $n$ 的残缺 $01$ 串，问有多少种补全方法，每次将连续三个位替换为它们的中位数后，能有一种方案使它变为 $1$。

$n\leq 3\times 10^5$

有一个 $n*m$ 矩形，初始全白。

现在进行 $nm$ 次操作，每次将一个格子涂黑，操作完输出有多少个子矩形里面没有黑格子。

$n,m\leq 500$