Quick and agile in both attack and defense, possessing the demeanor of a strategic planner, especially when the battlefield is open, those are all the characteristics of a light-weight main force on the chessboard — the bishop.

With these excellent features, it is extremely important to use the bishop skillfully in each game. To practice, Trung invested in buying a chessboard with size ~n~ ~\times~ ~m~ just to learn how to use the bishops. He has placed ~k~ bishops on the board, bishop number ~i~ is placed at position (~x_i~, ~y_i~), and he wants to place as many bishops as possible on the board, so that no two bishops can capture each other. The two bishops can only capture each other when they are positioned on the same diagonal.

Because the number of possible placements can be very large, Trung wants to try all possible ways to gain more experience for himself. Help Trung calculate the maximum number of bishops that can be placed on the board and the number of ways to do so, print the remainder of the number of ways after dividing by ~10^9+7~.

Input

The first line contains three integers ~n~, ~m~, and ~k~ (~1 \leq n \leq 16, 1 \leq m \leq 100, 0 \leq k \leq 100~) — the size of the chessboard and the number of bishops already on the board.

The ~k~ following lines contain two integers ~x_i~, ~y_i~ (~1 \leq x_i \leq n~, ~1 \leq y_i \leq m~) — the position of bishop number ~i~.

The data ensures that the ~k~ bishops Trung has placed do not capture each other.

Output

A single line containing two integers: the maximum number of bishops that can be placed and the number of ways to place the maximum number of bishops modulo ~10^9 + 7~.

Scoring

Sample Input 1

3 3 1
2 2

Sample Output 1

2 2

Sample Input 2

4 4 2
1 1
4 1

Sample Output 2

4 4

Sample Input 3

8 100 4
2 5
8 6
8 99
5 1

Sample Output 3

102 857399411

Notes

The green squares contain black bishops, which are the bishops already on the board. The white bishops are the bishops to be placed.