描述

弗里兰（Freeland）的字母表恰好由$N$个字母组成。弗里兰语（也称为弗里什语，Freish）的每个句子恰好由$M$个字母组成，且句子中没有单词分隔。所以，总共存在$N^M$个不同的弗里什语句子。

但是在小格拉斯（Mr. Grass Jr.）当选弗里兰总统后，一些冒犯他的单词被宣布为不可打印的，所有包含至少一个这些单词的句子都被禁止。如果单词$W$是句子$S$的子串，即存在$k \geq 1$，使得$S[k] = W[1]$，$S[k + 1] = W[2]$，...，$S[k + len(W) - 1] = W[len(W)]$，其中$k + len(W) - 1 \leq M$（$len(W)$表示单词$W$的长度），那么句子$S$就包含单词$W$。任何使用被禁止句子的人都将被判处 10 年监禁。

找出弗里兰人现在可以安全使用的不同句子的数量。

输入

输入文件的第一行包含三个整数：$N$（弗里什语字母表中的字母数量，$1 \leq N \leq 50$）、$M$（所有弗里什语句子的长度，$1 \leq M \leq 50$）和$P$（被禁止的单词数量，$0 \leq P \leq 10$）。

第二行恰好包含$N$个不同的字符，即弗里什语字母表中的字母（所有字符的 ASCII 码都大于 32）。

接下来的$P$行包含被禁止的单词，每个单词的长度不超过$\min(M, 10)$个字符，并且所有单词都仅由弗里什语字母表中的字母组成。

输出

输出唯一的一个整数，即弗里兰人可以安全使用的不同句子的数量。

输入数据 1

2 3 1
ab
bb

输出数据 1

5

来源

2001 年东北欧竞赛，北部分区