Cho một DFA đầy đủ. Hãy đếm số chuỗi độ dài đúng L trên bảng chữ cái được DFA chấp nhận. Vì kết quả có thể rất lớn, in phần dư theo 10^9+7. Sử dụng quy hoạch động: dp là véc-tơ số cách tới mỗi trạng thái sau khi đọc một số ký tự.
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
3
Output:
4
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 L.1 ≤ n ≤ 500, 1 ≤ k ≤ 26, 0 ≤ L ≤ 10^6.
In số chuỗi độ dài L được chấp nhận theo modulo 10^9+7.
Ví dụ:
Đầu vào:
2 2
1 0
0 1
0
1 1
3
Đầu ra:
4
Giải thích:
Đang tải editor...