Cho một DFA đầy đủ và một số N có thể rất lớn. Hãy đếm số chuỗi độ dài đúng N được chấp nhận, theo modulo 10^9+7. Vì N lớn, dùng lũy thừa ma trận: đặt ma trận đếm M[a][b] = số ký tự khiến a chuyển sang b, kết quả là hàng s của M^N cộng trên các trạng thái chấp nhận.
Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).
Ví dụ:
Input:
2 2
1 0
0 1
0
1 1
5
Output:
16
Khối mô tả DFA gồm:
n k — số trạng thái (đánh số 0..n-1) và kích thước bảng chữ cái.n dòng tiếp theo: dòng i gồm k số, số thứ j là trạng thái đích khi ở trạng thái i đọc ký tự thứ j.s.f rồi f số — tập trạng thái chấp nhận (nếu f=0 chỉ có số 0).
Sau khối DFA là một dòng chứa số nguyên N.1 ≤ n ≤ 80, 1 ≤ k ≤ 26, 0 ≤ N ≤ 10^18.
In số chuỗi độ dài N được chấp nhận, theo modulo 10^9+7.
Ví dụ:
Đầu vào:
2 2
1 0
0 1
0
1 1
5
Đầu ra:
16
Giải thích:
Đang tải editor...