题目背景

Minecraft 中有很多可爱的生物，比如 Creeper（又名 JJ 怪）和各种僵尸。当你没有足够的装备时，遇到它们只能逃跑。为了防止它们在你辛苦建造的房子旁边爆炸，你决定考察附近的地形，并设计一些迂回线路来应对多个怪物。

题目描述

给定一个有向图，图中边的长度均为 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,\quad k \leq 10^6, \quad 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. 环的路径需要按起始节点和经过的顺序区分，样例中的多个解说明了不同环的表示。