주방 배치

대형 은하 간 가구점 체인 Galactic-Мебель은 최근 LoST-2007 항성계의 주방 가구 시장에 진출했다. 이 항성계의 모든 아파트에서 주방은 $a$ 미터 곱하기 $b$ 미터 크기의 직사각형이다. 한쪽 벽을 따라 식탁을 놓고, 그와 인접한 벽에는 창문이 있다. 따라서 각종 주방 수납장을 놓을 수 있는 곳은 변의 길이가 $a$ 미터와 $b$ 미터인 모서리 공간이다.

공간을 아끼기 위해 이 항성계에서는 수납장을 서로 맞붙여 주방 모서리에 붙여 놓는다. 또한 수납장 자체는 벽 안에 매립되어, 벽을 따라 문짝만 보인다.

LoST-2007 항성계에서는 $n$ 종류의 주방 수납장을 사용한다. 각 종류의 수납장은 너비 $w_i$로 특징지어지며, 주방에는 각 종류의 수납장이 정확히 하나씩 있어야 한다.

최근 Galactic-Мебель의 마케팅 부서장은 고객에게 주방에 수납장을 배치하는 여러 가지 방법을 제안할 수 있다는 것을 알아냈다. 적어도 하나의 수납장 위치가 다른 배치는 서로 다른 것으로 본다. 서로 다른 종류의 수납장이 같은 너비를 가질 수 있지만, 외장 마감이 다르다. 따라서 너비가 같은 수납장의 위치만 다른 배치도 서로 다른 것으로 본다.

예를 들어 $a = 3$, $b = 4$이고 너비가 각각 1과 2인 두 종류의 수납장이 있다고 하자.

그러면 주방 배치가 여섯 가지 가능하다. 가능한 배치는 그림에 나와 있다.

주방과 수납장의 크기가 주어졌을 때 서로 다른 배치의 수를 구하라.

첫째 줄에 세 정수 $a$, $b$, $n$이 주어진다 ($1 \le a \le 300$, $1 \le b \le 300$, $1 \le n \le 100$). 다음 $n$개 줄에는 각각 정수 $w_i$가 주어지며, 이는 해당 수납장의 너비이다 ($1 \le w_i \le 300$).

서로 다른 주방 배치의 수를 출력한다.