← 返回题目列表

Codeforces · 2091/F

F. 伊戈尔和山

中文机器翻译题面 查看原题

IT校园“NEIMARK”的参观者不仅是实力强劲的程序员,更是身体强健的人!有的练游泳,有的练划船,有的练攀岩!

伊戈尔大师是当地攀岩界的杰出人物。有一天,他去爬山,想要登上其中一座山峰。作为一名经验丰富的登山者,伊戈尔决定不遵循既定路线,而是利用他的技能严格垂直攀登。

Igor 找到了山的一个矩形垂直剖面,并在心里将其分为 $$$n$$$ 个水平层。然后,他使用垂直分区将每个级别分成 $$$m$$$ 段。在检查这些部分时,伊戈尔发现了可以抓握的方便突起(以下简称为 成立)。因此,山的选定部分可以表示为 $$$n \times m$$$ 矩形,其中一些单元格包含保留点。

作为一名经验丰富的程序员,Igor 决定计算有效的数量 路线。路线被定义为一系列 不同 成立。如果满足以下条件,则认为路由有效:

  • 路线中的第一个货舱位于最底层($$$n$$$ 行);
  • 路线中的最后一个停靠点位于最顶层($$$1$$$ 行);
  • 后续每次持有不低于前一次;
  • 每个级别(即矩形的每一行)至少使用一次保持;
  • 每个级别最多使用两次握持(因为伊戈尔只有两只手);
  • 如果相应部分的中心之间的距离不超过伊戈尔的臂展,伊戈尔可以从当前保持到达下一个保持。

Igor 的臂展为 $$$d$$$,这意味着如果 欧几里得距离 相应线段的中心之间不超过$$$d$$$。 ($$$i_1, j_1$$$) 和 ($$$i_2, j_2$$$) 之间的距离由 $$$\sqrt{(i_1 - i_2) ^ 2 + (j_1 - j_2) ^ 2}$$$ 给出。

计算不同有效路线的数量。如果两条路线所使用的保留列表或访问这些保留的顺序不同,则它们被视为不同。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$、$$$d$$$ ($$$2 \leq n \leq 2000$$$、$$$1 \leq m、d \leq 2000$$$)。

以下 $$$n$$$ 行均包含 $$$m$$$ 个字符——对山峰相应级别的描述。符号“#”代表空段,符号“X”代表有保留的段。级别是从上到下描述的。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$4 \cdot 10^6$$$。

输出

对于每个测试用例,输出以 $$$998244353$$$ 为模的不同路线的数量。

示例

输入
复制

3
3 4 1
XX#X
#XX#
#X#X
3 4 2
XX#X
#XX#
#X#X
3 1 3
X
X
#

输出
复制

2
60
0

注意

第一种情况可能的路线:

在第二个例子中,Igor 的臂展变大了,所以他可以使用新的路线,例如这个:

在第三个示例中,下层没有保留,因此没有正确的路线。