VM 09 Bài 10 - Binary palindrome


Submit solution

Points: 1.95 (partial)
Time limit: 0.9s
Memory limit: 512M

Problem source:
VNOI Marathon 2009Round 4Problem Setter: Khúc Anh Tuấn
Problem type

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!

Input

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.

Output

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~.

Giới hạn

  • ~1 \leq N \leq 300~.
  • ~0 \leq K \leq 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~.

Sample Input

5 1
0

Sample Output

2

Note

  • 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~.

Comments


  • 1
    I_love_Hoang_Yen  commented on 2, May, 2021, 21:43

    Mình nghĩ bài này nên cho thêm 1 test ví dụ lớn hơn :(