問題背景

在 Minecraft 中，有許多可愛的生物，例如 Creeper（苦力怕）和各種殭屍。當你沒有足夠的裝備時，遇到牠們只能逃跑。為了防止牠們在你辛苦建造的房子旁邊爆炸，你決定勘察附近的地形，並設計一些迂迴路線來應對多個怪物。

問題描述

給定一個有向圖，圖中邊的長度均為 1，請計算總長度小於 $k$ 的環的個數，並將結果對 $m$ 取模。

需要注意的是，題目中的「不同環」定義請參考範例部分。保證圖中沒有自環（即對於所有 $i$，有 $g[i,i] = 'N'$）。

輸入格式

第一行包含一個整數 $n$，表示圖的節點個數。

接下來的 $n$ 行，每行長度為 $n$ 的字符串 $g$，其中：

• 如果 $g[i,j] = 'Y'$，表示存在從節點 $i$ 到節點 $j$ 的一條有向邊；
• 如果 $g[i,j] = 'N'$，表示從節點 $i$ 到節點 $j$ 沒有邊。

最後一行包含兩個整數 $k$ 和 $m$。

輸入數據範圍：

• $n \leq 100$
• $k \leq 10^6$
• $m \leq 10^9$

輸出格式

輸出一個整數，表示總長度小於 $k$ 的環的個數，對 $m$ 取模後的結果。

範例

輸入範例：

4
NYNY
NNYN
YNNN
YNNN
6 100

輸出範例：

12

範例解釋： 總共有 12 個不同的環如下所示：

• 長度為 2 的環：$(0,3), (3,0)$
• 長度為 3 的環：$(0,1,2), (1,2,0), (2,0,1)$
• 長度為 4 的環：$(0,3,0,3), (3,0,3,0)$
• 長度為 5 的環：$(0,1,2,0,3), (0,3,0,1,2), (1,2,0,3,0), (2,0,3,0,1), (3,0,1,2,0)$

提示

1. 請特別注意題目中的環不允許有自環（即 $g[i, i] = 'N'$ 恒成立）。
2. 環的路徑需要按起始節點和經過的順序區分，範例中的多個解釋明了不同環的表示。