Mô tả và yêu cầu

Cho 𝑁 + 1 xâu nhị phân có độ dài là 𝑀. Hãy đếm xem trong 𝑁 xâu ban đầu, có
bao nhiêu tập con có tổng 𝑂𝑅 bằng xâu thứ 𝑁 + 1. Vì kết quả có thể rất lớn nên
chỉ cần in ra phần dư khi chia cho 109 + 7 .

Dữ liệu vào

- Dòng đầu chứa 2 số N, .
- 𝑁 + 1 dòng tiếp theo, mỗi dòng chứa 1 xâu nhị phân có độ dài 𝑀.

Dữ liệu ra

- Một dòng duy nhất là kết quả tìm được.

Ví dụ

INPUT                                        OUTPUT
                         4 2          12
                         00
                         10
                         11
                         11
                         11



     Giải thích: Có 12 cách để chọn các tập sao cho tổng                               𝑂𝑅 là 11
     -    Cách 1: (1, 3)
     -    Cách 2: (1, 3, 4)
     -    Cách 3: (1, 4)
     -    Cách 4: (1, 2, 3)
     -    Cách 5: (1, 2, 4)
     -    Cách 6: (1, 2, 3, 4)
     -    Cách 7: (2, 3)
     -    Cách 8: (2, 4)
     -    Cách 9: (2, 3, 4)
     -    Cách 10: (3)
     -    Cách 11: (4)
     -    Cách 12: (3, 4)