Задача Censure. У країні Триляндії абетка складає перші N маленьких англійських літер, а по указу Президента всі слова пишуться без пропусків. Границі слів можна встановлювати довільним чином, але деякі (можливо й всі) слова, які складаються з трьох літер Міністерство Цензури заборонило для використання. Знайдіть кількість трилянських речень, що не містять жодного забороненого слова (тобто «цензурних»).

Технічні умови. Програма Censure читає з пристрою стандартного введення у першому рядку кількість літер у трилянській абетці N (2<=N<=26), у другому - кількість заборонених слів K (0<=K<=N3) та у третьому- довжину речення L (3<=L<=1000). Далі слідує K рядків, у кожному з яких міститься заборонене слово з трьох літер. Всі слова різні. Програма виводить кількість «цензурних» речень за модулем 1000000007.

Приклад

Введення

3

8

4

aaa

abc

aab

aac

aba

abb

aca

cca

Виведення

40

 

 

© LIKT 1998-2018