#2753. 分配房间

分配房间

Description

正整数1…N编号,房间i和房间j之间的距离为|i-j|。

现在总共有m名同学,用1…m编号,每个人选择一个房间住下。有些同学是好友,

就希望住的近一些,不是好友的就希望住的远一些。好友关系是双向的,并且能保证对应

的无向图是连通的。假如两位同学互为好友,他们住的房间距离就不能超过D,否则必须

严格大于D。

陶陶交给你的任务是:计算出有多少种分配房间的方案。由于答案可能很大,你只需

要输出答案mod1,000,000,007后的值。

Format

Input

第一行包含三个正整数N,M,D�。

下面�M行用于描述好友关系,第i行第j个字符表示编号为i的同学和编号为j是否为好

友,Y表示是好友,N表示不是好友。第i行第�j个字符一定为N,但没任何特殊含义。数

据保证一定满足题目的要求。

Output

包含一个非负整数,表示答案mod1,000,000,007后的值。

Samples

522
NY
YN
14

Limitation

N<=100,M<=50,D<=8