D. Сейф
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Вася пытается взломать сейф. Он знает, что код состоит из n цифр, причем каждая цифра — 0 или 1. Вася сделал m попыток ввести код. После каждой попытки система сообщала ему, в скольких позициях стоят правильные цифры. В каких именно позициях стоят неправильные цифры не сообщается. Вася был настолько неудачлив, что ни разу не ввел код, в котором было бы правильно более 5 цифр. Сейчас Вася совсем запутался — ему кажется, что в системе ошибка, и она противоречит самой себе. Помогите Васе — посчитайте, сколько осталось возможных вариантов кода, которые не противоречат предыдущим ответам системы.

Входные данные

В первой строке записано два целых числа n и m (6 ≤ n ≤ 35, 1 ≤ m ≤ 10) — количество цифр в коде и количество попыток, сделанных Васей. Далее следует m строк, в каждой из которых через пробел записаны si и ci — соответственно Васина попытка (строка из n цифр 0 или 1) и ответ системы (целое число от 0 до 5 включительно).

Выходные данные

Выведите одно число — сколько осталось вариантов кода, которые не противоречат m ответам системы.

Примеры
Входные данные
6 2
000000 2
010100 4
Выходные данные
6
Входные данные
6 3
000000 2
010100 4
111100 0
Выходные данные
0
Входные данные
6 3
000000 2
010100 4
111100 2
Выходные данные
1