Skewers

Witek is preparing skewers to grill. He has fixed a list of possible ingredients to thread onto the sticks, and now he is thinking about how to arrange them. He noticed that some ingredients cannot be placed right next to each other, because doing so ruins the taste. Likewise, certain combinations of three consecutive ingredients taste bad.

For example, let the letter a denote a piece of pineapple and the letter b a piece of lamb. Suppose that two pieces of pineapple next to each other are undesirable, and that three lamb pieces in a row are undesirable as well. We record these rules as the forbidden combinations aa and bbb.

A skewer is never flipped and is always eaten starting from the left end, so the order of the letters matters in the forbidden combinations too.

If we build a skewer with exactly 3 ingredients, then under the rules above there are 4 possible skewers: aba, abb, bab, bba.

Representing each ingredient by a lowercase letter, count the skewers of length exactly $n$ (that is, strings of length $n$) in which no forbidden two-letter combination appears in adjacent positions and no forbidden three-letter combination appears in consecutive positions, then output that count modulo $m$. There are $p$ available ingredients, corresponding to the first $p$ lowercase letters of the alphabet.

The first line of input contains a small integer $z$, the number of data sets that follow one after another.

Each data set has the following format.

The first line contains four space-separated integers $m$, $n$, $p$, $k$: the modulus, the length of the skewer, the number of distinct ingredients, and the number of forbidden combinations, respectively ($1 \le m, n \le 1000$, $1 \le p \le 26$, $0 \le k \le p^2 + p^3$).

Each of the next $k$ lines describes one forbidden combination. A forbidden two-letter combination is given as two lowercase letters, and a forbidden three-letter combination as three lowercase letters. If $\ell_j$ denotes the $j$-th lowercase letter of the alphabet, then every letter $\ell_j$ appearing in a combination satisfies $1 \le j \le p$.

For each data set, output on its own line the number of distinct skewers satisfying the conditions, taken modulo $m$.