题目描述

动物园里有什么？大老虎、大狮子、大灰狼…… 当这三种猛兽真的在动物园里相遇，就给园长出了个不小的难题。

具体来说，动物园里有一片 N行 M列的方格形场地，每格的状态可用字符 'X'或 '?'表示。'X'表示该格没有笼子，因此不能饲养猛兽；'?' 表示该格有笼子，可以饲养任意一只猛兽。

可供饲养的三种猛兽中，老虎是独居动物，不能与任何动物相邻；狼和狮子是群居动物，它们都只能与同类相邻。（如果任意两格有共同边，我们就称这两格相邻。）

糟糕的是，未来 T个月内，每个月都会有一只笼子损毁。也就是说，该笼子此前一直处于正常使用状态，但从该月起永久失效。数据保证，每个月都至少有一个可供使用的笼子，即不会所有笼子均失效。

园长想知道，要将场地内所有可供使用的笼子放满猛兽，每个月分别有多少种排布方案。（答案需对10⁹+7取模。）

输入描述

第 1 行为 3 个整数 N, M, T，表示场地有 N行 M列，要经过 T个月。

接下来 N行，每行 M个字符，均为 'X'或 '?'，表示每格的状态。

接下来 T 行，每行两个整数 R, C，表示第 R行第 C列的笼子将从该月起失效，不能再存放猛兽。

输出描述

共 T+1行，每行一个整数，为该月的可行排布方案数，答案需对 10⁹+7取模。

样例1

输入

3 4 2

?XX?

X??X

??X?

1 4 2 2

输出

54

18

54

样例2

输入

3 3 5

???

???

???

2 2

2 1

2 3

1 2

3 2

输出

2

2

2

4

18

81

提示

对于 20% 的数据，N = 1, T = 0;

对于 40% 的数据，0 < N, M≤100, T = 0;

对于 60% 的数据，0 < N, M≤100,,0≤T≤100;

对于 80% 的数据，0 < N, M≤1000, 0≤T≤1000;

对于 100% 的数据，0 < N, M≤1000, 0≤T≤10⁵.

第 1 行为 3 个整数 N, M, T，表示场地有 N行 M列，要经过 T个月。

接下来 N行，每行 M个字符，均为 'X'或 '?'，表示每格的状态。

接下来 T 行，每行两个整数 R, C，表示第 R行第 C列的笼子将从该月起失效，不能再存放猛兽。

对于 20% 的数据，N = 1, T = 0;

对于 40% 的数据，0 < N, M≤100, T = 0;

对于 60% 的数据，0 < N, M≤100,,0≤T≤100;

对于 80% 的数据，0 < N, M≤1000, 0≤T≤1000;

对于 100% 的数据，0 < N, M≤1000, 0≤T≤10⁵.