#P3785. 分配房间

    ID: 2988 传统题 1000ms 512MiB 尝试: 5 已通过: 5 难度: 9 上传者: 标签>CF2700省选/NOI-等价类划分有限候选集缩减暴力枚举状压 DP位计数滚动数组排列数计算

分配房间

题目描述

房间用正整数 1∼n1 \sim n 编号,房间 ii 和房间 jj 之间的距离为 ∣i−j∣|i-j|。

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

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

输入格式

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

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

输出格式

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

5 2 2
NY
YN
14

数据规模与约定

对于 100%100\% 的数据,n≤100n \le 100,m≤50m \le 50,d≤8d \le 8。