#MX162. Uniformly Distributed
Uniformly Distributed
时间限制:1000ms
空间限制:512MB
题目描述
有一个 行 列的网格,每个格子被涂成红色(R)、蓝色(B)或未涂色(.)。
现在要把所有未涂色的格子染成红色或蓝色。设未涂色格子的数量为 ,则共有 种染色方案。求有多少种染色方案满足以下条件:
从 出发,每次向右或向下移动一格,最终到达 。无论选择哪条路径,路径上经过的格子(包括起点和终点)中,红色格子的数量都相同。
答案对 取模。
输入格式
第一行两个正整数 。
接下来 行,每行一个长度为 的字符串,表示网格的状态。第 行第 个字符为 R 表示该格已涂成红色,为 B 表示已涂成蓝色,为 . 表示未涂色。
输出格式
输出一行一个整数,表示满足条件的染色方案数对 取模的结果。
样例
样例 1 输入
2 2
B.
.R
样例 1 输出
2
样例 1 说明
从 到 有两条路径:
若 和 染成不同颜色,两条路径经过的红色格子数不同,不满足条件;若染成相同颜色,则两条路径经过的红色格子数相同。因此答案为 。
样例 2 输入
3 3
R.R
BBR
...
样例 2 输出
0
样例 2 说明
可能不存在满足条件的染色方案。
样例 3 输入
2 2
BB
BB
样例 3 输出
1
样例 3 说明
没有未涂色的格子,且当前网格已经满足条件,因此答案为 。
数据范围
对于 的数据,, 仅由 R、B、. 组成。