Start: Dec, 22, 2016 20:15:00
2016年秋季学期程序设计基础第三次考试(八点补考)
End: Dec, 22, 2016 22:05:00
Time elapsed:
Time remaining:

Simple DNA 2183

Time Limit:  1 s      Memory Limit:   256 MB
Submission:1     AC:1     Score:15

Description

Landy是Simple DNA研究领域的专家。simple DNA的特点如下:
- Simple DNA具有与正常DNA无异的碱基序列。 

- Simple DNA的名字来源于两个原因:

    -它只有'A'和'B'两种碱基构成;

    -它的碱基序列长度最大值是30。 

- simple DNA的碱基序列长度为3的倍数。 

Landy的研究工作是寻找末尾具有指定终止密码子的特殊的Simple DNA。密码子表示为三个碱基序列的组合(最后三个碱基被指定)。他需要在给定长度L和可选的终止密码子的情况下,寻找满足条件的Simple DNA的个数。

Input

第一行一个整数L,为Simple DNA的碱基序列的长度。3<=L<=30 (L%3==0)。

第二行一个整数N,为可选的终止密码子的个数。1<=N<=8。

接下来一行,包含N个以空格分隔的密码子。各密码子仅含3个字符(仅含'A'或者'B')。

给定的终止密码子不重复。

Output

输出所有可能的Simple DNA的个数

Samples

input
6 1 AAB
output
8
input
3 3 AAA BBB BAB
output
3
input
18 5 AAA AAB ABB BAA BBA
output
163840

Hint

DNA中间出现终止密码子不影响题目要求,也计入个数。