题目描述

圣诞老人为了保护自己的 GPU，雇佣了胡桃夹子军队看守一个由 $R$ 行 $C$ 列组成的网格工作坊。

一个守卫站在某个格子时，可以看到自己所在的整行和整列。如果一个守卫看不到任何其他守卫，则称这个守卫是“孤独的”。

初始时，网格中已经有 $N$ 个守卫，位置互不相同。第 $i$ 个守卫位于第 $X_i$ 行、第 $Y_i$ 列。初始守卫不一定都是孤独的。

圣诞老人考虑在剩余的 $R\cdot C-N$ 个空格中继续放置守卫。每个空格可以选择放或不放，所以总共有

$$2^{R\cdot C-N}$$

种配置。

定义 $f(k)$ 为最终配置中恰好有 $k$ 个孤独守卫的方案数，对 $10^9+7$ 取模。

你需要求出所有：

$$k=0,1,\ldots,\min(R,C)$$

对应的 $f(k)$。

为了限制输出规模，请改为输出下列异或值：

$$g(0)\oplus g(1)\oplus\cdots\oplus g(\min(R,C)),$$

其中：

$$g(k)=(f(k)+1220)\cdot(k+2025),$$

$\oplus$ 表示按位异或。

输入格式

输入第一行包含整数 $T$，表示测试用例数。

每个测试用例：

• 第一行包含三个整数 $R,C,N$；
• 接下来 $N$ 行，第 $i$ 行包含两个整数 $X_i,Y_i$，表示已有守卫的位置。

输出格式

对于第 $i$ 个测试用例，输出：

Case #i: ans

其中 ans 为

$$g(0)\oplus g(1)\oplus\cdots\oplus g(\min(R,C)).$$

数据范围

$$1\le T\le80$$ $$1\le R,C\le10^6$$ $$0\le N\le\min(R\cdot C,10^6)$$ $$1\le X_i\le R$$ $$1\le Y_i\le C$$

同一测试用例中所有坐标 $(X_i,Y_i)$ 互不相同。

样例说明

第一组样例中，初始配置有 $N=3$ 个守卫，只有中间那个守卫是孤独的。

在继续放置守卫后：

• 有 $7$ 种配置使得 $k=0$；
• 有 $1$ 种配置使得 $k=1$，即不改变初始配置；
• 有 $0$ 种配置使得 $k=2$，因为添加更多守卫无法增加孤独守卫数量。

因此：

$$f(0)=7\pmod {10^9+7},\quad f(1)=1\pmod {10^9+7},\quad f(2)=0.$$

于是：

$$g(0)=(7+1220)(0+2025)=2,484,675,$$ $$g(1)=(1+1220)(1+2025)=2,473,746,$$ $$g(2)=(0+1220)(2+2025)=2,472,940.$$

最终答案为：

$$2,484,675\oplus2,473,746\oplus2,472,940=2,485,565.$$

样例输入

5
2 3 3
1 1
2 2
1 3
3 3 1
2 1
5 5 0
2 3 2
1 1
2 2
3 3 2
2 3
3 3

样例输出

Case #1: 2485565
Case #2: 692688
Case #3: 67352691244
Case #4: 2497554
Case #5: 846520