题目描述

房间用正整数 $1 \sim n$ 编号，房间 $i$ 和房间 $j$ 之间的距离为 $|i-j|$。

现在总共有 $m$ 名同学，用 $1 \sim m$ 编号，每个人选择一个房间住下。有些同学是好友，就希望住的近一些，不是好友的就希望住的远一些。好友关系是双向的，并且能保证对应的无向图是连通的。假如两位同学互为好友，他们住的房间距离就不能超过 $d$，否则必须严格大于 $d$。

陶陶交给你的任务是：计算出有多少种分配房间的方案。由于答案可能很大，你只需要输出答案 $\bmod 10^9+7$ 后的值。

输入格式

第一行包含三个正整数 $n,m,d$。

下面 $m$ 行用于描述好友关系，第 $i$ 行第 $j$ 个字符表示编号为 $i$ 的同学和编号为 $j$ 是否为好友，Y 表示是好友，N 表示不是好友。第 $i$ 行第 $i$ 个字符一定为 N，但没任何特殊含义。数据保证一定满足题目的要求。

输出格式

包含一个非负整数，表示答案 $\bmod 10^9+7$ 后的值。

522
NY
YN

14

数据规模与约定

对于 $100\%$ 的数据，$n \le 100$，$m \le 50$，$d \le 8$。