题目描述

西尔瓦尼亚的苏丹热爱举办派对，因为这能让他有理由装饰宫殿。他特别喜欢一种名为“彩带”的装饰品——由不同珠子串成的串饰，悬挂在天花板上。和大多数苏丹一样，他对所有事物都极为挑剔，包括这些串饰：具体来说，他只喜欢特定的珠子组合出现在彩带上。例如，若有4种不同的珠子（A、B、C、D），苏丹可能规定“今晚派对的彩带只能包含组合 ABB、BCA、BCD、CAB、CDD、DDA”。这显然极大限制了可能的彩带数量。比如，若彩带长度为5，唯一可能的串珠序列是 BCABB 和 BCDDA（像 ABBCA 这样的序列会被禁止，因为其中 BBC 不是允许的组合）。由于苏丹喜欢多样性，给定彩带长度和允许的珠子组合时，计算可能的彩带总数就变得很重要。

输入格式

输入包含多组测试用例，每组用例由两行组成：

1. 第一行包含三个正整数 n、l、m，分别表示珠子类型数、彩带长度、苏丹喜欢的组合数。其中 n、l、m 的最大值分别为26、100、600。
2. 第二行包含 m 个组合，每个组合长度相同（1到10之间），用空格分隔，仅由大写字母组成。
   输入以“0 0 0”结束，该输入行无需处理。

输出格式

对每组测试用例，输出一行表示可能的彩带总数，所有答案均在32位整数范围内。

输入样例 1

4 5 6  
ABB BCA BCD CAB CDD DDA  
5 4 5  
E D C B A  
4 8 3  
AA BB CC  
0 0 0  

输出样例 1

2  
625  
3  

题目来源

北美中东部地区竞赛（East Central North America 2003）