Hùng đang nghiên cứu về não bộ con người và cố gắng mô phỏng cách hoạt động của nó. Hùng dựng một mạng có ~n \times m + 2~ đỉnh, được đánh số từ 0 đến ~n \times m + 1~. Các đỉnh được chia thành ~n + 2~ lớp, đỉnh thứ ~i~ sẽ được xếp vào lớp thứ ~[\frac{i+m-1}{m}]~; tức là lớp thứ 0 và lớp thứ ~(n + 1)~ có một đỉnh, còn các lớp khác đều có ~m~ đỉnh. Sau đó, cậu thêm các cạnh có hướng vào mạng. Từng đỉnh của lớp thứ ~i~ sẽ được nối với từng đỉnh của lớp thứ ~(i + 1)~ ~(0 \le i \le n)~. Như vậy, mạng neuron của Hùng sẽ có ~m \times m \times (n - 1) + 2m~ cạnh có hướng.

Để giải quyết vấn đề, Hùng sẽ thêm ~k~ cạnh có hướng vào mạng. Để không tạo ra chu trình, các cạnh đều chỉ được nối từ lớp thấp đến lớp cao; tức là nếu một cạnh nối từ đỉnh ~i~ đến đỉnh ~j~ thì ~[\frac{i+m-1}{m}] < [\frac{j+m-1}{m}]~. Đồng thời, việc thêm các cạnh luôn đảm bảo rằng không có hai cạnh nào nối cùng một cặp đỉnh, tính cả cạnh cũ lẫn cạnh mới.

Yêu cầu: Tính số đường đi đơn khác nhau từ đỉnh 0 đến đỉnh ~n \times m + 1~ trên mạng sau khi đã thêm ~k~ cạnh.

Input

• Dòng đầu chứa ba số nguyên dương ~n, m, k~.
• Mỗi dòng trong số ~k~ dòng tiếp theo ghi hai số nguyên không âm ~i~ và ~j~ cho biết Hùng nối thêm một cạnh có hướng từ đỉnh ~i~ đến đỉnh ~j~.

Output

• Ghi một số nguyên duy nhất là số đường đi đơn khác nhau từ đỉnh 0 đến đỉnh ~n \times m + 1~ trên mạng.

Sample Input 1

3 2 2
0 4
1 5

Sample Output 1

11