2894: 环游世界
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：8
解决：5
题目描述
在Cai0715的世界里，总共有N个城市，每两个城市之间都被一条无向的道路连接。
某一天，Boboo来Cai0715的世界游玩，由于这个世界太过于神奇，使他产生了一种环游世界的冲动，但他必须按照下面的规则进行环游。
·他必须在一个城市开始环游，在另一个世界结束环游。
·他环游世界时必须经过所有的城市一次，且只能经过一次。
·他环游世界时必须经过N-1条道路，且只能经过N-1条道路。
·由于某些道路的风景非常漂亮，所以Boboo想要在他环游世界的过程中必须经过这些道路。
现在，给定你一些必须经过的道路，问Boboo环游世界的方案有多少种？
输入
第一行，一个数N，代表共有N个城市。
以下是一个N行N列的字符矩阵A，如果A[I][J]是Y则代表城市I和城市J之间这条道路必须被经过。
输出
一行，一个数，Boboo环游世界的方案数。由于最后答案可能很大，所以只需要将答案mod 1000000007 输出即可。
样例输入 复制
3
NYN
YNN
NNN样例输出 复制
4提示
【样例解释】
1、 1->2->3
2、 2->1->3
3、 3->1->2
4、 3->2->1
【数据范围】
对于30%的数据，2<=N<=5。
对于50%的数据，2<=N<=20。
对于100%的数据，2<=N<=50