Xâu Nhị Phân Tránh Tập Mẫu Cấm
Points
88
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Đề bài
Cho số nguyên dương $N$ ($1 \le N \le 10^{18}$) và $M$ xâu nhị phân cấm $P_1, P_2, \dots, P_M$ ($\sum |P_i| \le 9$). Hãy đếm số lượng xâu nhị phân độ dài $N$ không chứa bất kỳ xâu nào trong $M$ xâu cấm làm xâu con liên tiếp. In kết quả modulo $10^9 + 7$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N$ và $M$ ($1 \le N \le 10^{18}$, $1 \le M \le 9$).
- $M$ dòng tiếp theo, mỗi dòng chứa một xâu nhị phân $P_i$ ($1 \le |P_i|$, $\sum |P_i| \le 9$).
Dữ liệu ra
Một số nguyên duy nhất là số lượng xâu thỏa mãn modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 3 1 101 |
7 |
| 4 2 00 11 |
2 |
Giới hạn
- $1 \le N \le 10^{18}$
- $\sum |P_i| \le 9$
Community Discussion