Card Flipping Game

The card flipping game is a solitaire card game that uses two types of cards, A and B. Card A has the rules of the game written on it. Specifically, as shown in Figure 1, it has two integers $N$ and $M(\le N)$, and a pattern $P$ consisting of the characters 'O' and 'X' arranged in an $N \times N$ grid.

Figure 1

Card B has the character 'O' on its front and the character 'X' on its back. One card B is used to represent one character of the pattern written on card A, and enough cards B are prepared for this purpose.

Let us start the game. First, choose one card A, and according to the value of $N$ written on it, place cards B in an $N \times N$ grid. All cards placed initially must be placed so that 'X' is visible. Each placed card is identified by its row and column numbers as in Figure 2.

Figure 2

Once the initial placement of the cards is finished, the player repeats a 'flip', described below, as needed. One 'flip' consists of two steps.

• Step 1: In the $N \times N$ grid where the cards are placed, choose any one row or one column. Also, according to the integer $M$ written on card A, choose any integer $k(0 \le k < M)$.
• Step 2: If the choice in step 1 is row $i$, then for all $j$ with $j \equiv k \pmod{M}$, flip all cards at positions $(i,j)$ on the grid. Similarly, if the choice in step 1 is column $j$, then for all $i$ with $i \equiv k \pmod{M}$, flip all cards at positions $(i,j)$ on the grid.

The player must repeat 'flips' to make the pattern of the cards on the grid match the pattern $P$ drawn on card A. Determine whether this is actually possible.

• $1 \le M \le N \le 1\,000$
• Every character in $P$ is either 'O' or 'X'.