Cho một DFA đầy đủ. Hãy đếm tổng số chuỗi có độ dài từ 0 đến L (tính cả chuỗi rỗng) được DFA chấp nhận, theo modulo 10^9+7. Cộng dồn số chuỗi chấp nhận qua từng bước quy hoạch động.
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
2
Output:
3
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 tổng 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
2
Đầu ra:
3
Giải thích:
Đang tải editor...