Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3319
Islands

Time Limit: 1 Second      Memory Limit: 32768 KB

There are N islands and some directed paths between some of them. You are the transportation minister of these islands, and you are going to build some more directed paths so that every island belongs to exactly one cycle. A cycle is two or more islands I1, I2, I3, ... Ik, such that there are paths: I1 -> I2, I2 -> I3, ... and Ik -> I1. Besides the cycles, there should not be any extra edges. Of course, you cannot build a path from an island to itself. You want to calculate how many different ways you can build paths to satisfy the restriction.

Input

There are multiple cases (no more than 100). For each case, the first line is an integer N (1 <= N <= 100), giving the number of islands. N = 0 indicates the end of input. Then N lines follow, each with N characters, giving the paths between islands. The j-th character of the i-th line is either 'Y' or 'N'. 'Y' means there is a path from the i-th island to the j-th island, while 'N' means there is no path from the i-th island to the j-th island. The i-th character of the i-th line is always 'N'.

Output

For each case, you should output how many different ways you can build paths to satisfy the restriction. The answer may be very large, so just output the answer MOD 10,000,007.

Sample Input

2
NN
NN
2
NY
YN
3
NNN
NNN
NNN
3
NYY
NNN
NNN
0

Sample Output

1
1
2
0

Author: HANG, Hang
Source: The 10th Zhejiang University Programming Contest
Submit    Status