문제 배경

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. 사이클에는 자기 루프가 없어야 합니다 (즉, 모든 $i$에 대해 $g[i, i] = 'N'$가 성립합니다).
2. 사이클에서 노드를 순회하는 순서가 서로 다른 사이클을 구별하는 데 중요합니다. 예시에서 여러 서로 다른 해답이 나오는 것이 이를 설명합니다.