Кодовый замок. В разведывательное управление доставили сейф с секретной информацией, кодовый замок на котором открывается комбинацией из nn цифр, каждая цифра может принимать b различных значений от 0 до b−1. Код неизвестен, однако разведчики передали несколько донесений о том, что сумма цифр кода в некоторых заданных позициях равна какому‑то известному числу. Используя информацию из всех полученных донесений, определите, сколько существует возможных кодов, удовлетворяющих этим условиям. Формат входных данных Первая строка входных данных содержит число b количество различных значений одной цифры кода, 2≤b≤10. Вторая строка содержит число n количество цифр в коде, n≥1, bn≤60000. Третья строка содержит число t количество имеющихся донесений о сумме каких‑то цифр кода, t≥1.

Далее следует t строк, каждая из которых содержит два числа: pi и si (1≤pi≤n, 0≤si≤9) — номер позиции в коде и сумма цифр в этой позиции соответственно.

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

Пример Входные данные 3 4 2 1 2 3 4

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

Объяснение У нас 4 цифры в коде, каждая цифра может принимать значения от 0 до 2-1=1. Из условия следует, что сумма цифр в позициях 1 и 2 равна 2, а в позициях 3 и 4 равна 4. Возможные варианты кодов: 0110, 1010, 1100, 0021, 0201, 2001.