You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

棋盘上有一个过河卒，需要走到底线。卒行走的规则是可以向左移动一格，向右移动一格或者向前移动一格。同时在棋盘上有两个另一方的棋子，需要拦截这个卒走到底线。这两个棋子的走法和帅一致，可以走到前后左右四个方向上相邻的格子。因此本题可以称为「帅拦过河卒」。

题目描述

温情提醒：在本题中，红子和红子、红子和黑子之间不能初始时位于同一个位置，或者相撞。

有一个 $n$ 行 $m$ 列的棋盘。我们用 $(i, j)$ 表示第 $i$ 行第 $j$ 列的位置。棋盘上有一些障碍，还有一个黑棋子和两个红棋子。

游戏的规则是这样的：红方先走，黑方后走，双方轮流走棋。红方每次可以选择一个红棋子，向棋盘的相邻一格走一步。具体而言，假设红方选择的这个棋子位置在 $(i, j)$，那么它可以走到 $(i-1,j),(i+1,j),(i,j-1),(i,j+1)$ 中的一个，只要这个目的地在棋盘内且没有障碍且没有红方的另一个棋子。

黑方每次可以将自己的棋子向 三个方向之一 移动一格。具体地，假设这个黑棋子位置在 $(i,j)$，那么它可以走到 $(i−1,j),(i,j−1),(i,j+1)$ 这三个格子中的一个，只要这个目的地在棋盘内且没有障碍。

在一方行动之前，如果发生以下情况之一，则立即结束游戏，按照如下的规则判断胜负（列在前面的优先）：

• 黑棋子位于第一行。此时黑方胜。
• 黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。
• 当前玩家不能进行任何合法操作。此时对方胜。

现在假设双方采用最优策略，不会进行不利于自己的移动。也就是说:

• 若存在必胜策略，则会选择所有必胜策略中，不论对方如何操作，本方后续获胜所需步数最大值最少的操作。
• 若不存在必胜策略，但存在不论对方如何行动，自己都不会落败的策略，则会选择任意一种不败策略。
• 若不存在不败策略，则会选择在所有策略中，不论对方如何操作，对方后续获胜所需步数最小值最大的操作。

我们不关心复杂的策略，所以请你计数总共有多少个初始的两个红子和一个黑子的摆放位置，满足红方可以 恰好一步取得胜利。

因为答案可能很大，所以请对 $998244353$ 取模。

输入格式

从 zu.in 中读入数据。

第一行，两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串。在这些字符中：. 表示空位；# 表示障碍物。

输出格式

输出到 zu.out 中。

输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例

3 3
...
.##
...

32

样例 1 解释

如下图的初始局面可以满足「红方一步必胜」：

...
R##
.BR

但是，以下初始局面要么不合法，要么不满足「红方一步必胜」：

###
###
###

RBR
.##
...

RRR
B##
RRR

...
B##
.RR

聪明的读者不难发现，样例 $1$ 的正确输出即为 $32$。

附加样例

见 下发 的 zu/zu2.in 和 zu/zu2.ans 至 zu/zu5.in 和 zu/zu5.ans。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（20 pts）：$\max(n, m) \leq 10$。
• Subtask 2（20 pts）：保证不存在障碍。
• Subtask 3（30 pts）：$\max(n, m) \leq 100$。
• Subtask 4（30 pts）：无特殊限制。

对于所有数据，保证 $1 \leq n, m \leq 2\times 10^3$，保证字符串只含 . 和 # 两种字符。