| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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: | adm |
| 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 PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
