사이클의 개수

방향 그래프 $G$가 주어진다. 길이가 $K$보다 작은 서로 다른 사이클의 개수를 구하는 프로그램을 작성하시오. 이 개수는 매우 커질 수 있으므로 $M$으로 나눈 나머지를 출력한다.

사이클은 노드를 차례로 나열한 것이며, 같은 노드가 여러 번 나와도 된다. 각 노드에서 다음 노드로 가는 간선이 있어야 하고, 마지막 노드에서 첫 번째 노드로 가는 간선도 있어야 한다. 사이클의 길이는 나열한 노드의 개수이다. 나열 순서가 다르면 서로 다른 사이클로 센다. 예를 들어 $(0, 1, 2)$와 $(1, 2, 0)$은 서로 다른 사이클이다.

노드에는 $0$번부터 $N-1$번까지 번호가 붙어 있다.

첫째 줄에 그래프 $G$의 노드 개수 $N$과 $K$, $M$이 주어진다. ($1 \le N \le 35$, $1 \le K \le 10^6$, $1 \le M \le 10^9$)

둘째 줄부터 $N$개의 줄에 그래프의 간선 정보가 인접 행렬 형식으로 주어진다. $i$번째 줄의 $j$번째 문자는 $i$번 노드에서 $j$번 노드로 가는 간선 정보이다. Y는 간선이 있다는 뜻이고, N은 간선이 없다는 뜻이다. 입력으로 주어지는 그래프에는 루프가 없다. 즉 $i$번째 줄의 $i$번째 문자는 항상 N이다.

첫째 줄에 길이가 $K$보다 작은 서로 다른 사이클의 개수를 $M$으로 나눈 나머지를 출력한다.

첫 번째 예제에서 길이가 $6$보다 작은 사이클은 다음과 같다.

• $(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)$