Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BINPAL - Binary palindrome

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), 1010101 (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ó 23 = 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.

ãy

Được gửi lên bởi:VOJ Team
Ngày:2009-07-31
Thời gian chạy:0.600s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon 2009
Round 4
Problem Setter: Khúc Anh Tuấn

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.