BINPAL - Binary palindrome

Giới hạn
  • Thời gian: 0.6s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Nhà vua của đất nước VNOI rất yêu thích tin học và nghệ thuật. Ngài rất quan tâm đến những xâu nhị phân đối xứng. Xâu nhị phân đối xứng là xâu chỉ gồm 2 loại ký tự 0, 1 và xâu không thay đổi dù ta đọc theo thứ tự từ trái sang phải hay từ phải sang trái.

Trong bữa tiệc sinh nhật lần thứ 101 của nhà vua, ngài đã đưa ra một danh sách gồm K xâu nhị phân cho các vị đại thần. Sau đó ngài đặt ra câu hỏi: có bao nhiêu xâu nhị phân thoả mãn đồng thời 2 điều kiện:

  • Đó là xâu nhị phân đối xứng có đúng N ký tự.
  • Xâu không chứa 2 xâu con không giao nhau nằm trong danh sách K xâu nhị phân kia.

Ví dụ, nếu nhà vua đưa ra danh sách gồm 2 xâu nhị phân 101 và 1001 thì một vài xâu nhị phân không thoả mãn điều kiện thứ 2 là: 1011001 (chứa 2 xâu 101 và 1001), 101 0 101 (2 xâu con có thể giống nhau). Những xâu nhị phân thoả mãn điều kiện thứ 2 có thể là: 1001001 (2 xâu 1001 giao nhau), 1010011.

Các bạn hãy giúp các vị đại thần trả lời câu hỏi hóc búa của đức vua!

Dữ liệu

  • Dòng đầu ghi 2 số N, K.
  • K dòng sau, mỗi dòng ghi một xâu nhị phân trong danh sách mà nhà vua đã đưa ra.

Kết quả

  • Số lượng xâu nhị phân thoả mãn, chỉ cần in ra phần dư của kết quả khi chia cho 1000000007 .

Ví dụ

Input:
5 1
0
Output:
2

Giải thích

  • Có 2 3 = 8 xâu nhị phân đối xứng có độ dài 5. Do xâu không thể có 2 ký tự 0 nên chỉ có 2 xâu thoả mãn là 11111 và 11011.

Giới hạn

  • 1 ≤ N ≤ 300.
  • 0 ≤ K ≤ 30.
  • Độ dài của mỗi xâu trong input không vượt quá 30.
  • Trong 30% số test, N không vượt quá 30.

  • Người up: voj
  • Nguồn bài: VNOI Marathon 2009Round 4Problem Setter: Khúc Anh Tuấn