题目描述

一家旅馆有 $N$ 个房间，编号为 $0,1,\ldots,N-1$。房间 $i$ 与房间 $j$ 的距离定义为 $|i-j|$。

有 $M$ 只猫需要入住，每只猫恰好入住一个房间，并且任意两只猫不能住在同一个房间。

给定一个 $M\times M$ 的友情矩阵 friendship：friendship[i][j] 为 Y 表示猫 $i$ 与猫 $j$ 是朋友，为 N 表示不是朋友。友情关系对称、无自环，并且友情图连通。

还给定整数 $D$。房间安排必须满足：

• 若猫 $i,j$ 是朋友，则它们房间编号之差的绝对值不超过 $D$；
• 若猫 $i,j$ 不是朋友，则它们房间编号之差的绝对值必须严格大于 $D$。

求满足所有要求的房间分配方案数，对 $1,000,000,007$ 取模。

猫有编号，因此交换两只猫的房间会得到不同方案。

输入格式

第一行三个整数 $M,N,D$。

接下来 $M$ 行，每行一个长度为 $M$ 的字符串，表示友情矩阵。

输出格式

输出一个整数，表示合法房间分配方案数对 $1,000,000,007$ 取模后的结果。

样例

输入

2 5 2
NY
YN

输出

14

输入

4 58 1
NYYY
YNNN
YNNN
YNNN

输出

0

数据范围

$1\le N\le100$，$1\le D\le8$，$1\le M\le50$，且 $M\le N$。友情矩阵对称，主对角线均为 N，并保证友情图连通。