
ZOJ Problem Set  3319
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 I_{1}, I_{2}, I_{3}, ... I_{k}, such that there are paths: I_{1} > I_{2}, I_{2} > I_{3}, ... and I_{k} > I_{1}. 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 jth character of the ith line is either 'Y' or 'N'. 'Y' means there is a path from the ith island to the jth island, while 'N' means there is no path from the ith island to the jth island. The ith character of the ith 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 