Description

Xiao C decides to plant a pattern of the letters $\texttt{CCF}$ in his garden, so he wants to know how many planting schemes there are for the letters $\texttt C$ and $\texttt F$ respectively. Unfortunately, there are some pits in the garden where flowers cannot be planted, so he hopes you can help solve this problem.

The garden can be viewed as a grid with $n \times m$ positions, with rows numbered $1$ to $n$ from top to bottom, and columns numbered $1$ to $m$ from left to right. Each position may be a pit or not. Use $a_{i,j} = 1$ to indicate that there is a pit at row $i$, column $j$, and use $a_{i,j} = 0$ otherwise.

A planting scheme is called $\texttt{C-}$ shaped if there exist $x_1, x_2 \in [1, n]$ and $y_0, y_1, y_2 \in [1, m]$, satisfying $x_1 + 1 < x_2$ and $y_0 < y_1, y_2 \leq m$, such that the segments from columns $y_0$ to $y_1$ on row $x_1$, from columns $y_0$ to $y_2$ on row $x_2$, and from rows $x_1$ to $x_2$ on column $y_0$ are all not pits, and flowers are planted only on these positions.

A planting scheme is called $\texttt{F-}$ shaped if there exist $x_1, x_2, x_3 \in [1, n]$ and $y_0, y_1, y_2 \in [1, m]$, satisfying $x_1 + 1 < x_2 < x_3$ and $y_0 < y_1, y_2 \leq m$, such that the segments from columns $y_0$ to $y_1$ on row $x_1$, from columns $y_0$ to $y_2$ on row $x_2$, and from rows $x_1$ to $x_3$ on column $y_0$ are all not pits, and flowers are planted only on these positions.

Examples of $\texttt{C-}$ shaped and $\texttt{F-}$ shaped planting schemes are shown in the explanation of Sample 1.

Now Xiao C wants to know, given $n$, $m$, and the values $\{a_{i,j}\}$ indicating whether each position is a pit, how many possible $\texttt{C-}$ shaped and $\texttt{F-}$ shaped planting schemes there are, respectively. Since the answer may be very large, you only need to output the result modulo $998244353$. See the output format section for details.

Input Format

The first line contains two integers $T, id$, denoting the number of test cases and the test point ID, respectively. If the input is a sample, it is guaranteed that $id = 0$.

Then there are $T$ test cases. In each test case:

• The first line contains four integers $n, m, c, f$, where $n$ and $m$ denote the number of rows and columns of the garden, respectively. The meanings of $c$ and $f$ are described in the output format section.
• The next $n$ lines each contain a string of length $m$ consisting only of $0$ and $1$. The $j$-th character of the $i$-th string denotes $a_{i,j}$, i.e., whether the cell at row $i$, column $j$ in the garden is a pit.

Output Format

Let the numbers of $\texttt{C-}$ shaped and $\texttt{F-}$ shaped planting schemes in the garden be $V_C$ and $V_F$, respectively. For each test case, output one line with two non-negative integers separated by a space, representing $(c \times V_C) \bmod 998244353$ and $(f \times V_F ) \bmod 998244353$, respectively, where $a \bmod P$ denotes $a$ modulo $P$.

1 0
4 3 1 1
001
010
000
000

4 2

Hint

【Explanation of Sample 1】

The four $\texttt{C-}$ shaped planting schemes are:

**1 **1 **1 **1
*10 *10 *10 *10
**0 *** *00 *00
000 000 **0 ***

Here $\texttt*$ denotes planting a flower at that position. Note that the two horizontal strokes of $\texttt C$ do not need to have the same length.

Similarly, the two $\texttt{F-}$ shaped planting schemes are:

**1 **1
*10 *10
**0 ***
*00 *00

【Sample 2】

See the attachments $\texttt{plant/plant2.in}$ and $\texttt{plant/plant2.ans}$.

【Sample 3】

See the attachments $\texttt{plant/plant3.in}$ and $\texttt{plant/plant3.ans}$.

【Constraints】

For all test cases, it is guaranteed that $1 \leq T \leq 5$, $1 \leq n, m \leq 10^3$, $0 \leq c, f \leq 1$, and $a_{i,j} \in \{0, 1\}$.

Special property A: $\forall 1 \leq i \leq n, 1 \leq j \leq \left\lfloor \frac{m}{3} \right\rfloor$, $a_{i, 3 j} = 1$.

Special property B: $\forall 1 \leq i \leq \left\lfloor \frac{n}{4} \right\rfloor, 1 \leq j \leq m$, $a_{4 i, j} = 1$.

Translated by ChatGPT 5