新規
編集
添付
時間制限:5000ミリ秒
メモリ制限:10000KB
問題 
フリーランドのアルファベットは、N文字のみを用いている。フリーランド語、別名Freishのそれぞれの文は、区切り文字なしで正確にM文字からなる。ゆえに、N^M個のFreishの異なる文が存在する。
しかし、最近のグラスJr.氏のフリーランド大統領選の後に、彼を怒らせるいくつかの語は印刷に適さないとされ、それらのうちの1つ以上を含むすべての文は禁止された。禁止された文を用いた者は、懲役10年の刑に処される。
フリーランドの住民が、刑務所行きになる危険がないような異なる文が何種類あるかを求めよ。
入力
入力の最初の行は、3つの整数N(Freishアルファベットの文字の数)、M(あらゆるFreishの文の長さ)、P(禁止された単語の数)を含んでいる。但し、1 <= N <= 50, 1 <= M <= 50, 0 <= P <= 10である。
2行目は、Freishアルファベットを表すN個の異なる文字を含んでいる。すべての文字は、32より大きいアスキーコードを持つ。
続くP行は、禁止された単語を含んでいる。それぞれの長さは、min(M, 10)以下であり、すべてFreishアルファベットの文字のみを含んでいる。
出力
フリーランドの住民が安全に用いることができる異なる文の数を表す1つの整数を出力せよ。
入力の例
2 3 1 ab bb
出力の例
5
出典
Northeastern Europe 2001, Northern Subregion
