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ó. Theo cậu, khi một giác quan nhận được một tín hiệu, nó sẽ kích thích một số neuron (tế bào thần kinh) bằng xung điện, các neuron này lại kích thích các neuron khác có liên kết với nó bằng cách chia xung điện thành các xung nhỏ hơn và truyền qua các liên kết. Như vậy khi bị kích thích - như nhìn thấy một con mèo chẳng hạn, một tổ hợp các neuron sẽ bị kích thích ở một cường độ nhất định nào đó, tạo nên khái niệm con mèo trong ý thức. Lần sau nếu gặp một tín hiệu tương tự - nhìn thấy một con chó chẳng hạn, một tổ hợp neuron khác gần giống như cũ bị kích thích, ta có khái niệm về chó với nhiều nét tương đồng với mèo: Có lông, đuôi dài, bốn chân, ...

Hùng quyết định sẽ mô phỏng lại quá trình hoạt động này ở một cấp độ đơn giản hơn, phục vụ cho quá trình nghiên cứu. Đầu tiên, cậu dựng một mạng có ~n \cdot m+2~ đỉnh, được đánh số từ ~0~ đến ~n \cdot 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ứ ~\left[\frac{i+m-1}{m}\right]~; 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 \cdot m \cdot (n-1)+2m~ cạnh có hướng. Theo cậu, đỉnh ~0~ như là một giác quan nơi tiếp nhận các tín hiệu từ môi trường; các cạnh có hướng là các liên kết thần kinh giữa các neuron. Khi đỉnh ~0~ phát đi một tín hiệu, tuỳ thuộc vào đặc điểm của tín hiệu và trạng thái mạng, tín hiệu này sẽ được truyền đến đỉnh ~n \cdot m+1~ theo một đường đi đơn nào đó. Vì đây là sự mô phỏng ở dạng rất đơn giản nên số tổ hợp khác nhau của các đỉnh nằm trên đường đi không đủ lớn để đặc trưng cho nhiều khái niệm khác nhau (chính xác thì có ~m^n~ khái niệm có thể được mô tả).

Để 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ì ~\left[\frac{i+m-1}{m}\right] < \left[\frac{j+m-1}{m}\right]~. Đồ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. Hùng xem đây là quá trình mở rộng khái niệm của mạng, tương tự như quá trình học tập và hình thành các liên kết thần kinh mới ở người. Bây giờ, cậu cần đánh giá mức độ hiệu quả của việc mở rộng. Hãy giúp hùng tính số khái niệm khác nhau mà mạng neuron của cậu có thể mô tả sau khi thêm ~k~ cạnh. Tức là, tính số đường đi đơn khác nhau từ đỉnh ~0~ đến đỉnh ~n \cdot m+1~ trên mạng.

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 \cdot m+1~ trên mạng.

Scoring

Trong tất cả các test: ~3 \le n \le 10^{12}~; ~1 \le m \le 10^5~; ~1 \le k \le 10^5~.

Sample Input 1

3 2 2
0 4
1 5

Sample Output 1

11