問題文

A君はとても単純なDNAで知られるsimpleDNAの研究をしています。
simpleDNAの特徴は次のようなものです。

・simpleDNAは普通のDNAと同じく分岐しない塩基配列を持ちます。
・simpleDNAはとてもシンプルなので'A'と'B'の２種の塩基で構成されています。
・simpleDNAはとてもシンプルなので塩基配列の長さはせいぜい30までです。
・simpleDNAの塩基配列の長さはかならず3の倍数です。

このようなsimpleDNAからA君は次のようなsimpleDNAを探しています。

・塩基配列の末端が指定された終止コドンで終わるもの。

コドンとは3つの塩基配列の組み合わせのことを言います。
要は、最後の3つの塩基配列が終止コドンとして指定されるということです。
長さ$L$と候補の終止コドンがいくつか指定されます。
このような条件を満たすsimpleDNAは何パターンありうるでしょうか？

※なお、普通のDNAについての説明はこちらをご覧ください。
http://en.wikipedia.org/wiki/DNA

入力

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

$L$はsimpleDNAの塩基配列の長さです。$3\le L \le 30$。($L$は3の倍数。)
$N$は終止コドンの候補の数です。$1\le N \le 8$。
$S_i$は$i$番目の終止コドンの候補です。
$S_i$は必ず'A'または'B'で構成される3文字の文字列です。
終止コドンの候補には複数同じものが含まれません。

出力

A君が見つけることのできるsimpleDNAの配列のパターン数を1行で出力せよ。
最後に改行を忘れずに。

サンプル

6
1
AAB

8

3
3
AAA BBB BAB

3

18
5
AAA AAB ABB BAA BBA

163840