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 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.
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'.
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.
2 NN NN 2 NY YN 3 NNN NNN NNN 3 NYY NNN NNN 0
1 1 2 0
Author: HANG, Hang
Source: The 10th Zhejiang University Programming Contest