Chessboard Streets: Count Your Ways to School

In your city, the streets form a chessboard-like grid. There are \(a\) north-south streets, numbered from 1 to \(a\) from west to east, and \(b\) east-west streets, numbered from 1 to \(b\) from south to north. The intersection of the \(i\)-th north-south street and the \(j\)-th east-west street is denoted by \((i,j)\).

You live at \((1,1)\) and attend school at \((a,b)\). You ride your bicycle to school and can only move along the streets in the east or north direction.

There are \(N\) intersections under construction: \((X_1, Y_1)\), \((X_2, Y_2)\), \(\ldots\), \((X_N, Y_N)\). These intersections are closed to traffic. Determine the total number of valid paths from your home to school while avoiding the blocked intersections.

inputFormat

The first line contains three integers \(a\), \(b\), and \(N\) representing the number of north-south streets, east-west streets, and the number of blocked intersections, respectively.

Each of the following \(N\) lines contains two integers \(X_i\) and \(Y_i\) representing the coordinates of a blocked intersection.

outputFormat

Output a single integer that represents the total number of valid paths from \((1,1)\) to \((a,b)\) while avoiding all the blocked intersections.

sample

3 3 1
2 2

2