AT_arc025_4 [ARC025D] コンセント

[problemUrl]: https://atcoder.jp/contests/arc025/tasks/arc025_4 Anti Real Corporation 社は、日々の生活をちょっと変わった方法で充実させようと奮闘する組織である。 Anti Real Corporation 社のコンセント差込口はちょっと変わった形状をしている。コンセント差込口は縦に $ H $ 行、横に $ W $ 列の穴が並んだ形状をしている。コンセントプラグは、未使用の穴のうち、上下または左右に連続した $ 2 $ 箇所を使用することができる。言い変えると、上から $ i $ 番目、右から $ j $ 番目の穴を ($ i $,$ j $) と呼ぶことにすると、 - ($ i $,$ j $) と ($ i+1 $,$ j $) ($ 1\ ≦\ i\ ≦\ H-1 $, $ 1\ ≦\ j\ ≦\ W $) の $ 2 $ つの穴を選んで使用する。 - ($ i $,$ j $) と ($ i $,$ j+1 $) ($ 1\ ≦\ i\ ≦\ H $, $ 1\ ≦\ j\ ≦\ W-1 $) の $ 2 $ つの穴を選んで使用する。 コンセントプラグを差し込むにあたって、複数のコンセントプラグが同じ穴を同時に共有したり、コンセントキャップ（後述）が付いている穴を使用することはできない。 社長はある日、コンセントへの差し込みに面白さを与えるため、$ N $ 日間、営業開始時刻に以下の動作のうちどちらか $ 1 $ つを行うことにした。 - 未使用な穴を $ 1 $ つ選び、その穴にコンセントキャップを差し込む。 - コンセントキャップが差し込まれている穴を $ 1 $ つ選び、コンセントキャップを取り除き未使用状態にする。 最初、どの穴も未使用であるとする。 社長は部長に、$ N $ 日間のそれぞれの営業日において、コンセントへの差し込み方が全部で何通りあるのかを記録し、最終日に調査結果を報告するよう指示した。組み合わせについて、コンセントプラグ同士、コンセントキャップ同士は区別しないものとし、コンセントプラグを $ 1 $ つも使用しないものも $ 1 $ 通りとして数えるとする。 ところがこのことを締めきり直前まで忘れてしまっていた部長は、偶然にも残されていたコンセントキャップの履歴から、どうにかそれぞれの日についての結果を求めることにした。 すべての組み合わせを虱潰しに調べているようでは間に合わなさそうなので、開発班のあなたに、プログラムを書くように依頼があった。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ N $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ : $ S_N $ $ T_N $ - $ 1 $ 行目には、コンセント差込口の形状を表す $ 2 $ つの整数 $ H\ (1\ ≦\ H\ ≦\ 2) $ と $ W\ (1\ ≦\ W\ ≦\ 10^{11}) $ が空白区切りで与えられる。これはコンセント差込口が縦 $ H $ 行横 $ W $ 列に穴が並んだ形状をしていることを表す。 - $ 2 $ 行目には操作日程を表す整数 $ N\ (1\ ≦\ N\ ≦\ 20,000) $ が与えられる。 - $ 3 $ 行目から $ N $ 行では、操作についての情報が与えられる。このうち $ i $ 行目では、$ i $ 日目に行う動作を表す $ 2 $ つの整数 $ S_i\ (1\ ≦\ S_i\ ≦\ H) $ と $ T_i\ (1\ ≦\ T_i\ ≦\ W) $ が与えられる。これは、この日の営業開始時刻より前の段階で ($ S_i $, $ T_i $) が未使用なら、その日の営業開始時にコンセントキャップを差し込むことを、そうでないならコンセントキャップを取り除くことを表す。

$ N $ 行にわたって出力せよ。$ N $ 行のうち $ i $ 行目には、$ i $ 日目の営業開始時の操作後において、考えられるコンセントの配置の総数を $ 1000000007\ (=\ 1,000,000,007) $ で割った余りを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ W\ ≦\ 5,000\ ,\ N\ ≦\ 3,000 $ を満たすデータセット $ 1 $ に正解した場合は、$ 10 $ 点が与えられる。 - $ W\ ≦\ 100,000\ ,\ N\ ≦\ 3,000 $ を満たすデータセット $ 2 $ に正解した場合は、上記とは別に $ 30 $ 点が与えられる。 - 追加制約のないデータセット $ 3 $ に正解した場合は、上記とは別に $ 60 $ 点が与えられる。 ### Sample Explanation 1 第 $ 1 $ 日目の操作の後、以下のような配置になっている。この図において、六角形で表された場所はコンセントキャップがある場所であることを表す。 !\[\](/img/arc/025/4-1.png) よって、以下の $ 10 $ 通りの配置が考えられる。 !\[\](/img/arc/025/4-2.png)