Маленький Q і великі числа#9285

Маленький Q і великі числа

1 секунда

128 мегабайтів

Дуже складна

Маленький Q обожнює додатні великі цілі числа в системі числення $k$ , але не всі з них. Він не любить числа, які містять нулі, включаючи провідні нулі. Також він ретельно ставиться до кількості входжень кожної цифри. Формально його вподобання описуються двійковою матрицею $g_{1.. k - 1, 0.. n}$ g_{1..k-1,0..n}. Для кожної цифри $i$ від $1$ до $k - 1$ k - 1, якщо $g_{i, j} = 0$ g_{i,j} = 0, то йому не подобаються числа, які містять рівно $j$ копій цифри $i$ . Він також не допускає, щоб будь-яка цифра зустрічалася більше $n$ разів. Число повинно містити хоча б одну цифру.

Вподобання Маленького Q змінюються щодня. Є $m$ днів, у день $i$ значення $g_{u_{i}, v_{i}}$ g_{u_i,v_i} змінюється на протилежне ( $0$ стає $1$ і $1$ стає $0$ ). Нехай $c n t (i)$ позначає кількість великих цілих чисел, які подобаються Маленькому Q після $i$ -го дня змін, а $c n t (0)$ позначає відповідь до всіх змін. Ваше завдання — обчислити наступне значення:

Вхідні дані

Перший рядок містить три цілі числа $k$ , $n$ і $m$ : основу, верхню межу і кількість днів ( $3 \leq k \leq 10$ 3 \leq k \leq 10, $1 \leq n \leq 1.4 \cdot 1 0^{4}$ 1 \leq n \leq 1.4 \cdot 10^4, $1 \leq m \leq 200$ 1 \leq m \leq 200). У наступних $k - 1$ k - 1 рядках рядок $i$ містить $n + 1$ n + 1 цілих чисел $g_{i, 0}, g_{i, 1}, \dots, g_{i, n}$ g_{i,0}, g_{i,1}, \ldots, g_{i,n} ( $0 \leq g_{i, j} \leq 1$ 0 \leq g_{i,j} \leq 1). Разом вони задають початкову матрицю $g$ . Далі слідують $m$ рядків, $i$ -ий рядок містить два цілі числа $u_{i}$ u_i і $v_{i}$ v_i, що означають, що в $i$ -ий день значення $g_{u_{i}, v_{i}}$ g_{u_i,v_i} змінюється на протилежне ( $1 \leq u_{i} \leq k - 1$ 1 \leq u_i \leq k - 1, $0 \leq v_{i} \leq n$ 0 \leq v_i \leq n).

Вихідні дані

Виведіть одне ціле число: відповідь до задачі.

Приклади

Приклад 1