网格填数

题号：NC21346
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

有一个

的网格，第

行第

列的元素记为

,上面填满了数字，但是由于某些原因，有些数字缺失了
已知网格本来是满足如下的性质的
1：对于所有满足条件的 $({r},c) (0 \le H-n,0 \le c < W)$

是个奇数

2: 对于所有满足条件的 $({r},c) (0 \le r < H,0 \le c \le W-m)$

是个奇数

现在给你缺失数据的网格以及

和

，你需要将缺失的地方填成数字，请问有多少种填法可以满足网格本来的性质
输出方案数对

取模

输入描述:

第一行输入
接下来行每行输入个字符，缺失的位置用'.'表示

输出描述:

输出一个整数

示例1

输入

复制

2 2 2 2 
12
2.

输出

复制

示例2

输入

复制

2 2 2 2
21
1.

输出

复制

示例3

输入

复制

3 3 1 1
...
...
...

输出

复制

示例4

输入

复制

2 6 2 3
..58..
..47..

输出

复制

示例5

输入

复制

4 8 4 4
...1.2.3
4.5.6...
...7.8.9
1.2.3...

输出

复制

886073030

示例6

输入

复制

20 20 10 10
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

输出

复制

240076532

备注:

子任务1: H*W <= 100
子任务2: H*W <= 1000
子任务3: 无限制