#P11053. [2016杭电多校]A Simple Chess

    ID: 10195 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>CF2100提高格路计数Lucas 定理阶乘逆元预处理计数 DP补集计数

[2016杭电多校]A Simple Chess

A Simple Chess

Problem Description

There is a n×mn\times m board, a chess want to go to the position (n,m)(n, m) from the position (1,1)(1, 1). The chess is able to go to position (x2,y2)(x_2, y_2) from the position (x1,y1)(x_1, y_1), only and if only x1,y1,x2,y2x_1, y_1, x_2, y_2 is satisfied that $(x_2 - x_1)^2+(y_2 - y_1)^2 = 5, ~x_2 > x_1,~ y_2 > y_1$. Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle. I want you to tell me, There are how may ways the chess can achieve its goal.

Input

The input consists of multiple test cases. For each test case: The first line is three integers, $n, m, r, (1\leq n, m\leq 10^{18}, 0 \leq r\leq 100)$, denoting the height of the board, the weight of the board, and the number of the obstacles on the board. Then follow rr lines, each lines have two integers, x,y(1≤x≤n,1≤y≤m)x, y(1\leq x\leq n, 1\leq y\leq m), denoting the position of the obstacles. please note there aren't never a obstacles at position (1,1)(1, 1).

Output

For each test case,output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer after module 110119110119.

Sample Input

1 1 0
3 3 0
4 4 1
2 1
4 4 1
3 2
7 10 2
1 2
7 1

Sample Output

Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 1
Case #5: 5

Author

UESTC

Source

2016 Multi-University Training Contest 6