Mouse Journey

Είστε ένα ποντίκι που ζει μέσα σε ένα κλουβί σε ένα μεγάλο εργαστήριο. Το εργαστήριο αποτελείται από ένα ορθογώνιο πλέγμα τετράγωνων κλουβιών, με συνολικά ~R~ σειρές και ~C~ στήλες από κλουβιά ~(1 \le R,\;C \le 25)~.

Για να γυμναστείτε, οι ιδιοκτήτες του εργαστηρίου σας επιτρέπουν να μετακινείστε μεταξύ των κλουβιών. Μπορείτε να μετακινηθείτε μεταξύ των κλουβιών είτε μετακινούμενοι δεξιά μεταξύ δύο γειτονικών κλουβιών στην ίδια σειρά, είτε μετακινούμενοι προς τα κάτω μεταξύ δύο γειτονικών κλουβιών στην ίδια στήλη. Δεν μπορείτε να μετακινηθείτε διαγώνια, αριστερά ή προς τα πάνω.

Το κλουβί σας βρίσκεται σε μια γωνία του εργαστηρίου, η οποία έχει την ετικέτα ~(1,\;1)~ (για να υποδείξει την πιο πάνω σειρά και την πιο αριστερή στήλη). Θα θέλατε να επισκεφθείτε τον αδελφό σας που ζει στο κλουβί με την ένδειξη ~(R,\;C)~ (πιο κάτω σειρά, πιο δεξιά στήλη), το οποίο βρίσκεται στην άλλη γωνία διαγώνια. Ωστόσο, υπάρχουν κάποια κλουβιά από τα οποία δεν μπορείτε να περάσετε, επειδή περιέχουν γάτες.

Ο αδελφός σας, που λατρεύει τους αριθμούς, θα ήθελε να μάθει πόσες διαφορετικές διαδρομές υπάρχουν μεταξύ του κλουβιού σας και του δικού του που δεν σας βάζουν να πέρασετε μέσα από κανένα κλουβί γάτας. Γράψτε ένα πρόγραμμα για τον υπολογισμό αυτού του αριθμού των διαδρομών χωρίς γάτες.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει δύο ακέραιους αριθμούς ~R~ και ~C~, χωρισμένους με κενό διάστημα, που αντιπροσωπεύουν τον αριθμό σειρών και στηλών (αντίστοιχα). Στη δεύτερη γραμμή της εισόδου θα βρίσκεται ο ακέραιος ~K~, ο αριθμός των κλουβιών που περιέχουν γάτες. Οι επόμενες ~K~ γραμμές περιέχουν η καθεμία τη θέση βάση σειράς και στήλης (με αυτή τη σειρά) για ένα κλουβί που περιέχει μια γάτα. Κανένα από τα ~K~ κλουβιά με γάτες δεν επαναλαμβάνεται και όλα τα κλουβιά είναι έγκυρες θέσεις. Σημειώστε επίσης ότι τα ~(1,\;1)~ και ~(R,\;C)~ δεν θα είναι κλουβιά με γάτες.

Έξοδος

Εξάγετε τη μη αρνητική ακέραια τιμή που αντιπροσωπεύει τον αριθμό των διαδρομών μεταξύ του κλουβιού σας στη θέση ~(1,\;1)~ και του κλουβιού του αδελφού σας στη θέση ~(R,\;C)~. Μπορείτε να υποθέσετε ότι η τιμή της εξόδου θα είναι αυστηρά μικρότερη από ~1\;000\;000\;000~.

Παραδείγματα

input

2 3
1
2 1

output

2

input

3 4
3
2 3
2 1
1 4

output

1