E. Расшифровка генома
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Недавно был осуществлен совершенно секретный полет на Марс, в результате которого удалось получить некоторые сведения относительно марсианской ДНК. Стало известно, что любая марсианская цепочка ДНК содержит не более m различных нуклеотидов, пронумерованных от 1 до m. Из-за особенностей марсианской ДНК некоторые пары нуклеотидов не могут идти подряд в этой цепочке. Например, если нуклеотид номер 1 и нуклеотид номер 2 не могут встречаться подряд в марсианской ДНК, значит цепочка нуклеотидов [1, 2] не является корректной цепочкой марсианской ДНК, при этом цепочка нуклеотидов [2, 1] может быть корректной (если нет соответствующего ограничения). Количество пар нуклеотидов, которые не могут содержаться в цепочке ДНК подряд, равно k.

Для нужд генных исследований понадобилась информация о количестве корректных цепочек марсианской ДНК длины n. Вам поручено написать программу, которая вычислит это значение.

Входные данные

В первой строке записаны три целых числа через пробел n, m, k (1 ≤ n ≤ 1015, 1 ≤ m ≤ 52, 0 ≤ k ≤ m2).

В следующих k строках записаны по два символа, без пробела между ними, обозначающие запрещенную пару нуклеотидов. Первый символ обозначает первый нуклеотид в запрещенной паре, второй символ — второй нуклеотид.

Нуклеотиды, которым присвоены номера от 1 до 26 обозначаются буквами латинского алфавита от «a» до «z» (1 — «a», 2 — «b», ..., 26 — «z»). Нуклеотиды, которым присвоены номера от 27 до 52 обозначаются буквами латинского алфавита от «A» до «Z» (27 — «A», 28 — «B», ..., 52 — «Z»).

Гарантируется, что каждая запрещенная пара задана во входных данных не более одного раза. Гарантируется, что номера нуклеотидов в запрещенных парах не превосходят m. Обратите внимание, что в парах нуклеотидов важен порядок.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

Выведите единственное целое число — остаток от деления искомого количества на 1000000007 (109 + 7).

Примеры
Входные данные
3 3 2
ab
ba
Выходные данные
17
Входные данные
3 3 0
Выходные данные
27
Входные данные
2 1 1
aa
Выходные данные
0
Примечание

Во втором тестовом примере допустимы все возможные ДНК из трех нуклеотидов. Каждый нуклеотид может принимать одно из трех значений, поэтому всего существует 27 различных ДНК из трех нуклеотидов.

В третьем тестовом примере нельзя сделать ни одного ДНК из двух нуклеотидов — единственный возможный нуклеотид «a» не может встречаться два раза подряд.