Задача . Кодовый замок

В разведывательное управление доставили сейф с секретной информацией, кодовый замок на котором открывается комбинацией из n цифр, каждая цифра может принимать b различных значений от 0 до b − 1. Код неизвестен, однако разведчики передали несколько донесений о том, что сумма цифр кода в некоторых заданных позициях равна какому-то известному числу. Используя информацию из всех полученных донесений, определите, сколько существует возможных кодов, удовлетворяющих этим условиям.

Формат входных данных
Первая строка входных данных содержит число b — количество различных значений одной цифры кода, 2 ≤ b ≤ 10. Вторая строка содержит число n — количество цифр в коде, n \(\geq\) 1, bⁿ ≤ 60 000. Третья строка содержит число t – количество имеющихся донесений о сумме каких-то цифр кода, t \(\geq\) 1.
Следующие 2t строк содержат информацию об имеющихся донесениях. Каждое донесение состоит из двух строк. Первая из этих строк («маска цифр») содержит n символов, записанных слитно и равных «0» или «1», где цифра «1» обозначает, что в донесении говорится об этой цифре кода. Например, маска цифр «01011» означает сумму цифр, стоящих в коде на 2-й, 4-й и 5-й позициях. Во второй строке донесения записано число s, равное сумме цифр кода, стоящих на данных позициях. Гарантируется, что каждая маска цифр содержит хотя бы одну единицу и что все маски цифр различаются. Общее число донесений может быть любым, удовлетворяющим этим условиям.

Формат выходных данных
Программа должна вывести одно целое число — количество различных кодов, которые удовлетворяют всем донесениям.

Замечание
В примере из условия каждая цифра кода может принимать 8 различных значений от 0 до 7, код состоит из 3 цифр. Получены 2 донесения, из первого донесения известно, что сумма первой и второй цифры кода равна 7, из второго донесения известно, что сумма второй и третьей цифры кода равна 12. Существуют 3 кода, удовлетворяющие этим условиям: «075», «166», «257».