Problem Statement

A-kun is researching simpleDNA, which is known as a very simple kind of DNA.
The characteristics of simpleDNA are as follows.

・Like ordinary DNA, simpleDNA has a base sequence that does not branch.
・Since simpleDNA is very simple, it consists of only two kinds of bases, 'A' and 'B'.
・Since simpleDNA is very simple, the length of its base sequence is at most 30.
・The length of the base sequence of simpleDNA is always a multiple of 3.

Among such simpleDNA, A-kun is looking for simpleDNA of the following kind.

・The base sequence ends with a specified stop codon.

A codon is a combination of 3 bases in a sequence.
In short, the last 3 bases of the sequence are specified as a stop codon.
The length $L$ and several candidate stop codons are given.
How many patterns of simpleDNA satisfying these conditions are possible?

* For an explanation of ordinary DNA, see the following page.
http://en.wikipedia.org/wiki/DNA

Input

$L$
$N$
$S_1\ S_2\ \dots\ S_n$

$L$ is the length of the base sequence of simpleDNA. $3\le L \le 30$. ($L$ is a multiple of 3.)
$N$ is the number of candidate stop codons. $1\le N \le 8$.
$S_i$ is the $i$-th candidate stop codon.
$S_i$ is always a string of 3 characters consisting of 'A' or 'B'.
The candidate stop codons do not contain duplicates.

Output

Output on one line the number of patterns of simpleDNA sequences that A-kun can find.
Do not forget the newline at the end.

Sample

6
1
AAB

8

3
3
AAA BBB BAB

3

18
5
AAA AAB ABB BAA BBA

163840