Problem Description

Anti Real Corporation is an organization that strives to enrich daily life through unconventional methods.

The power outlet sockets of Anti Real Corporation have a unique shape. The sockets are arranged in a grid with $ H $ rows and $ W $ columns. A power plug can use two consecutive unused holes either vertically or horizontally. In other words, if we denote the hole at the $ i $-th row and $ j $-th column as ($ i $, $ j $), then:

• ($ i $, $ j $) and ($ i+1 $, $ j $) ($1 \leq i \leq H-1$, $1 \leq j \leq W$) can be used.
• ($ i $, $ j $) and ($ i $, $ j+1 $) ($1 \leq i \leq H$, $1 \leq j \leq W-1$) can be used.

When inserting a power plug, multiple plugs cannot share the same hole simultaneously, and holes with caps (described later) cannot be used.

One day, the president decided to add趣味to the insertion of power plugs by performing one of the following actions at the start of business each day for $ N $ days:

• Choose an unused hole and insert a power cap into it.
• Choose a hole with a power cap and remove the cap to make it unused.

Initially, all holes are unused.

The president instructed the chief to record the number of possible configurations for each day and report the findings on the last day. Combinations are considered indistinguishable, and not using any power plugs counts as one possibility.

However, the chief forgot about this until the last minute and decided to determine the results for each day from the accidentally left power cap history.

Since checking all combinations exhaustively seems infeasible, the development team has asked you to write a program.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ N $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ : $ S_N $ $ T_N $

• The first line contains two integers $H\ (1 \leq H \leq 2)$ and $W\ (1 \leq W \leq 10^{11})$, representing the shape of the power outlet sockets.
• The second line contains an integer $N\ (1 \leq N \leq 20,000)$, representing the number of days.
• The next $ N $ lines contain information about the operations. The $ i $-th line contains two integers $S_i\ (1 \leq S_i \leq H)$ and $T_i\ (1 \leq T_i \leq W)$, indicating that if ($ S_i $, $ T_i $) is unused before the start of the business on the $ i $-th day, a power cap will be inserted; otherwise, the cap will be removed.

Output Format

Output $ N $ lines. The $ i $-th line should contain the total number of possible power plug configurations after the operation on the $ i $-th day, modulo $1000000007\ (=\ 1,000,000,007)$.

Sample Input and Output

Sample Input #1

2 3
3
1 1
2 3
1 1

Sample Output #1

10
5
10

Sample Input #2

2 4
5
1 2
1 1
2 2
2 1
1 4

Sample Output #2

27
17
7
7
3

Notes/Hints

Partial Points

This problem has partial points:

• $ 10 $ points are awarded for solving the dataset where $W \leq 5,000$ and $N \leq 3,000$.
• An additional $ 30 $ points are awarded for solving the dataset where $W \leq 100,000$ and $N \leq 3,000$.
• An additional $ 60 $ points are awarded for solving the dataset without additional constraints.

Sample Explanation 1

After the operation on the first day, the configuration is as follows, where hexagons represent holes with power caps. Therefore, there are $ 10 $ possible configurations.

见题面 Input 部分

见题面 Output 部分