动物园里有什么
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
动物园里有什么？大老虎、大狮子、大灰狼……当这三种猛兽真的在动物园里相遇，就给园长出了个不小的难题。
具体来说，动物园里有一片 N 行 M 列的方格形场地，每格的状态可用字符 'X' 或 '?' 表示。'X' 表示该格没有笼子，因此不能饲养猛兽；'?' 表示该格有笼子，可以饲养任意一只猛兽。
可供饲养的三种猛兽中，老虎是独居动物，不能与任何动物相邻；狼和狮子是群居动物，它们都只能与同类相邻。（如果任意两格有共同边，我们就称这两格相邻。）
糟糕的是，未来 T 个月内，每个月都会有一只笼子损毁。也就是说，该笼子此前一直处于正常使用状态，但从该月起永久失效。数据保证，每个月都至少有一个可供使用的笼子，即不会所有笼子均失效。
园长想知道，要将场地内所有可供使用的笼子放满猛兽，每个月分别有多少种排布方案。（答案需对 取模。）
输入格式
第 1 行为 3 个整数 N, M, T，表示场地有 N 行 M 列，要经过 T 个月。
接下来 N 行，每行 M 个字符，均为 'X' 或 '?'，表示每格的状态。
接下来 T 行，每行两个整数 R, C，表示第 R 行第 C 列的笼子将从该月起失效，不能再存放猛兽。
输出格式
共 T+1 行，每行一个整数，为该月的可行排布方案数，答案需对 取模。
输入输出样例
3 4 2
?XX?
X??X
??X?
1 4
2 2
54
18
54
3 3 5
???
???
???
2 2
2 1
2 3
1 2
3 2
2
2
2
4
18
81
样例 1 解释
初始状态下，左上角、右上角和右下角的笼子均无相邻，因此各有 3 种可能。其余 4 个笼子只能全放狮子或全放狼，不能存放老虎，因此共 3 × 3 × 3 × 2 = 54 种排布方案。
第 1 个月后，右上角的笼子失效，其余笼子无变化，共 3 × 3 × 2 = 18 种方案。
第 2 个月后，第 2 行第 2 列的笼子也失效，新的状态如下图所示：
?XXX
XX?X
??X?
此时，左上角、右下角和第 2 行第 3 列的笼子不与其他相邻，各有 3 种可能。左下角有两个笼子相邻，只能一起存放狮子或狼。因此共 3 × 3 × 3 × 2 = 54 种方案。
数据范围与约定
对于 20% 的数据，
对于 40% 的数据，
对于 60% 的数据，
对于 80% 的数据，
对于 100% 的数据，