你是某家非常成功的剧院的导演。你最喜欢威廉·莎士比亚，尽管他倾向于创作血腥的结局。关于他的一些剧作——比如《哈姆雷特》和《李尔王》——人们常说，如果它们再多一幕，就不得不从观众席的第一排开始杀人了。

现在，你快要因为莎士比亚没有写出这最后一幕而对他产生怨恨了。这是因为刚刚有 $2k$ 个人来到了你的剧院。他们是 $k$ 对名人——足球运动员、模特、YouTube 主播——他们似乎并不完全理解戏剧表演的含义。每一对名人都极有可能在演出期间引发激烈的争吵，从而彻底破坏演出。但有一个解决办法——这取决于你如何为他们分配座位，如果一对名人没有被分配到相邻的座位，那么发生争吵的可能性就会小得多。

剧院礼堂由 $n$ 行 $m$ 列的座位组成。有些座位已经被“普通”观众预订了，你不想让他们换座位。共有 $k$ 对名人，你必须为每一位名人分配一个座位，使得没有任何一对名人占据两个相邻的座位（我们认为两个座位相邻仅当它们共享一条公共边，即一个在另一个的旁边或前后）。为了让自己振作起来，请计算出你可以这样做的总方案数——这通常是一个非常大的数字，所以只需要计算其对 $10^9 + 7$ 取模后的结果。如果任何一位名人被分配到了不同的座位，则认为两种分配方案是不同的。请注意，我们区分所有的名人（认为他们是不相同的）。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 100$)。接下来是各测试用例的描述。 每个测试用例的第一行包含三个正整数 $n, m, k$ ($1 \le n \cdot m \le 144, 1 \le k \le mn/2$)，分别表示行数、每行的座位数以及名人对数。接下来的 $n$ 行描述了座位情况——每一行都是一个由字符 ‘X’ 和 ‘.’ 组成的字符串，其中 ‘.’ 表示空座位，‘X’ 表示已被占用的（不可用的）座位。你可以假设至少有 $2k$ 个空座位。

输出格式

对于每个测试用例，输出一个数字——在没有一对名人被分配到相邻座位的情况下，为名人分配座位的方案总数，结果对 $10^9 + 7$ 取模。

样例

输入 1

2
2 2 2
..
..
4 4 3
X.X.
....
.X..
...X

输出 1

8
347040

说明

在第一个样例中，所有的分配方式如下所示（‘A’ 和 ‘a’ 表示分配给第一对名人的座位，‘B’ 和 ‘b’ 表示分配给第二对名人的座位）：

AB Ab ab aB BA bA ba Ba ba Ba BA bA ab aB AB Ab