#P3250. Light Switches

Light Switches

Problem Background

In Minecraft, there are many cute creatures like Creepers and different types of zombies. When you don't have enough equipment, the only option when encountering them is to run away. To prevent them from exploding near the house you worked hard to build, you decide to explore the nearby terrain and design some detour routes to deal with multiple monsters.

Problem Description

Given a directed graph where the length of all edges is 1, calculate the number of cycles with a total length less than kk, and return the result modulo mm.

Note that the definition of "different cycles" is crucial, so please refer to the examples for clarification. It is guaranteed that the graph does not have self-loops (i.e., for all ii, g[i,i]=Ng[i, i] = 'N').

Input Format

The first line contains an integer nn, representing the number of nodes in the graph.

The next nn lines each contain a string of length nn. In each string:

  • If g[i,j]=Yg[i,j] = 'Y', it means there is a directed edge from node ii to node jj;
  • If g[i,j]=Ng[i,j] = 'N', it means there is no edge from node ii to node jj.

The last line contains two integers kk and mm.

Input constraints:

  • n100n \leq 100
  • k106k \leq 10^6
  • m109m \leq 10^9

Output Format

Output a single integer representing the number of cycles with a total length less than kk, modulo mm.

Example

Input Example:

4
NYNY
NNYN
YNNN
YNNN
6 100

Output Example:

12

Explanation: There are 12 distinct cycles as follows:

  • Cycles of length 2: (0,3),(3,0)(0,3), (3,0)
  • Cycles of length 3: (0,1,2),(1,2,0),(2,0,1)(0,1,2), (1,2,0), (2,0,1)
  • Cycles of length 4: (0,3,0,3),(3,0,3,0)(0,3,0,3), (3,0,3,0)
  • Cycles of length 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)$

Notes

  1. Pay special attention that cycles cannot have self-loops (i.e., g[i,i]=Ng[i, i] = 'N' holds for all ii).
  2. The order in which the nodes are traversed in the cycle is important for distinguishing different cycles, as shown in the example where multiple distinct solutions are listed.