Xâu Nhị Phân Tránh Tập Mẫu Cấm

Buổi 59 — Lũy thừa ma trận
Points
88
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Submissions
Đề 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$
Draft saved