/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
H 行 W 列のマス目の各マスに X, Y のいずれかの文字が書かれています．
上から i 行目，左から j 列目のマスを (i, j) で表します．
マス目に書かれている文字は H 個の文字列 S_1, S_2, \dots, S_H によって与えられ，S_i の j 文字目がマス (i, j) に書かれた文字を表します．
下または右に隣接するマスへの移動を繰り返してマス (1, 1) からマス (H, W) に至る経路 P に対して，
- 「 P で通るマスに書かれた文字を順に並べて得られる長さ (H + W - 1) の文字列」を \mathrm{str}(P) とし，
- 「 \mathrm{str}(P) 中で
Y同士が隣り合う箇所の個数の 2 乗」を P のスコアと定義します．
そのような経路 P としてあり得るものは \displaystyle\binom{H + W - 2}{H - 1} 通りありますが，その全てに対するスコアの総和を 998244353 で割った余りを求めてください．
\binom{N}{K} の意味
\displaystyle\binom{N}{K} は，N 個の相異なる要素から K 個を選ぶ場合の数を表す二項係数です．制約
- 1 \leq H \leq 2000
- 1 \leq W \leq 2000
- S_i \ (1 \leq i \leq H) は
X,Yからなる長さ W の文字列である．
入力
入力は以下の形式で標準入力から与えられる．
H W S_1 S_2 \vdots S_H
出力
あり得る経路全てに対するスコアの総和を 998244353 で割った余りを出力せよ．
入力例 1
2 2 YY XY
出力例 1
4
経路 P としてあり得るものは (1, 1) \to (1, 2) \to (2, 2) と (1, 1) \to (2, 1) \to (2, 2) の 2 通りです．
- (1, 1) \to (1, 2) \to (2, 2) の場合，\mathrm{str}(P) = {}
YYYであり，1, 2 文字目と 2, 3 文字目の 2 箇所でY同士が隣り合っているので，スコアは 2^2 = 4 です． - (1, 1) \to (2, 1) \to (2, 2) の場合，\mathrm{str}(P) = {}
YXYであり，Y同士が隣り合う箇所は無いので，スコアは 0^2 = 0 です．
したがって，求める総和は 4 + 0 = 4 となります．
入力例 2
2 2 XY YY
出力例 2
2
2 通りのいずれの経路の場合も \mathrm{str}(P) = {}XYY であり，スコアは 1^2 = 1 です．
入力例 3
10 20 YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY
出力例 3
423787835
スコアの総和を 998244353 で割った余りを出力してください．
Score : 600 points
Problem Statement
There is a grid with H rows and W columns where each square has one of the characters X and Y written on it.
Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The characters on the grid are given as H strings S_1, S_2, \dots, S_H: the j-th character of S_i is the character on square (i, j).
For a path P from square (1, 1) to square (H, W) obtained by repeatedly moving down or right to the adjacent square, the score is defined as follows.
- Let \mathrm{str}(P) be the string of length (H + W - 1) obtained by concatenating the characters on the squares visited by P in the order they are visited.
- The score of P is the square of the number of pairs of consecutive
Ys in \mathrm{str}(P).
There are \displaystyle\binom{H + W - 2}{H - 1} such paths. Find the sum of the scores over all those paths, modulo 998244353.
What is \binom{N}{K}?
\displaystyle\binom{N}{K} is the binomial coefficient representing the number of ways to choose K from N distinct elements.Constraints
- 1 \leq H \leq 2000
- 1 \leq W \leq 2000
- S_i \ (1 \leq i \leq H) is a string of length W consisting of
XandY.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Print the sum of the scores over all possible paths, modulo 998244353.
Sample Input 1
2 2 YY XY
Sample Output 1
4
There are two possible paths P: (1, 1) \to (1, 2) \to (2, 2) and (1, 1) \to (2, 1) \to (2, 2).
- For (1, 1) \to (1, 2) \to (2, 2), we have \mathrm{str}(P) = {}
YYY, with two pairs of consecutiveYs at positions 1, 2 and 2, 3, so the score is 2^2 = 4. - For (1, 1) \to (2, 1) \to (2, 2), we have \mathrm{str}(P) = {}
YXY, with no pairs of consecutiveYs , so the score is 0^2 = 0.
Thus, the sought sum is 4 + 0 = 4.
Sample Input 2
2 2 XY YY
Sample Output 2
2
For either of the two possible paths P, we have \mathrm{str}(P) = {}XYY, for a score of 1^2 = 1.
Sample Input 3
10 20 YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY
Sample Output 3
423787835
Print the sum of the scores modulo 998244353.