Description

给定一有向图，边长均为1，求长度小于k的环的个数mod m。

保证有向图中无自环(即g[i,i]='N')。

什么样的环属于不同的解，详见样例解释。

Format

Input

第一行n表示节点个数

接下来n行长度为n的字符串,g[i,j]='Y'表示i到j有一条边，g[i,j]='N'则说有i到j之间没有边

最后一行两个整数k，m。

n<=100, k<=10^6, m<=10^9

Output

一个整数表示答案.

Samples

4
NYNY
NNYN
YNNN
YNNN
6 100

12  

Hint【样例解释】

12个解分别为：(0,3) ; (3,0) ; (0,1,2) ; (1,2,0) ;

(2,0,1);(0,3,0,3) ;

(3,0,3,0) ; (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)。