Vẫn là siêu trộm marvinthang, lần này cậu phải đối đầu với chiếc két sắt của ~Suzuki~ ~Jirokichi~ . Với sự giàu có của tập đoàn ~Suzuki~ , ông ~Jirokichi~ đã mua được một chiếc két sắt cực kì an toàn và khó mở.

Sau khi tiếp cận và điều tra, marvinthang biết được mã số của két sắt là một dãy nhị phân độ dài ~n~ (có ~n~ kí tự bao gồm ~0~ và ~1~). Cậu đã thử nhập ~m~ mã số, nhưng điều bất ngờ là sau mỗi lần nhập, hệ thống két sắt phản hồi lại và cho biết số lượng vị trí đúng của mã cậu vừa nhập (tức là số vị trí mà giá trị của mã vừa nhập và mã của két sắt giống nhau).

marvinthang đen đủi tới mức mà cậu không nhập nổi mã số nào có hơn ~5~ vị trí đúng. Bây giờ cậu hoàn toàn trở nên hoang mang, cậu nghi ngờ rằng đây chỉ là một trò lừa bịp~!?!!~.

Bạn hãy giúp marvinthang đếm số lượng mã số mà thỏa mãn các phản hồi của hệ thống.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~6\leq n \leq 35, 1\leq m \leq 10~) - lần lượt là độ dài của mã số và số lần thử của marvinthang.

~m~ dòng tiếp theo, mỗi dòng chứa ~s_i~ và ~c_i~ cách nhau bởi dấu cách tương ứng là mã số mà marvinthang đã nhập (gồm ~n~ kí tự ~0~ và ~1~) và phản hồi của hệ thống (~0 \leq c_i \leq 5~).

Output

In ra một số nguyên duy nhất là số lượng mã số thỏa mãn các phản hồi của hệ thống.

Sample Input 1

6 3
101010 2
111001 3
110110 3

Sample Output 1

5

Notes