Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P162PROC - ROUND 2C - Ghép xâu

Skull Knight rất thích chơi với các xâu chữ. Bố của Skull Knight là Deadth Kight, ông có rất nhiều chữ cái thuộc 52 loại, và ông đánh số như sau: “a” đến “z” ông lần lượt đánh số từ 1 đến 26; “A” đến “Z” được đánh số từ 26 đến 52.

Deadth Knight cho Skull Knight m loại chữ cái có chỉ số từ 1 đến m, mỗi loại đều có thể dùng vô số lần. Và Skull Knight được ghép tùy thích m chữ cái trên thành 1 xâu ký tự có độ dài là n. Nhưng cậu ta không thích 1 vài cặp chữ cái, ví dụ cậu không thích cặp ký tự (a, b), thì cậu ta sẽ không ghép bất kỳ xâu nào có xâu con là “ab” (Lưu ý cặp (a,b) và cặp (b,a) là 2 cặp phân biệt)

Hỏi Skull Knight có thể ghép được tất cả bao nhiêu xâu ký tự thỏa mãn?

Input

Dòng đầu tiên bao gồm 3 số nguyên n, m, k (1 <= n <= 1015, 1 <= m <= 52, 0 <= k <= m2). Trong đó n là độ dài xâu ký tự cần ghép, m là số loại ký tự mà Skull được bố cho, k là số cặp ký tự mà Skull Knight không thích.

K dòng tiếp theo, mỗi dòng gồm 1 xâu ký tự có 2 chữ cái là cặp chữ cái mà Skull không thích.

Input đảm bảo 1 cặp được nhập nhiều nhất 1 lần, chỉ số của các chữ cái trong cặp không vượt quá m. Lưu ý cặp (a, b) khác cặp (b, a)

Output

In ra số nguyên là kết quả của đề bài. Do kết quả lớn nên hãy lấy dư cho 1000000007 (109 + 7)

Example

Test 1:

Input:

3 3 2

ab

ba

 

Output:

17

 

Test 2:

Input:

3 3 0

 

Output:

27

 

Test 3:

Input:

2 1 1

aa

 

Output:

0


Được gửi lên bởi:Admin
Ngày:2016-02-20
Thời gian chạy:1s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.