Returning Prince

On the country of Checkering, there were a Queen and her beloved son, a Prince. After months of hardworking, the Queen thinks that the Prince deserves some vacation, so the Queen gives the Prince k days to go for some trip and on the k-th day, the Prince should have already come back to the castle.

Country of Checkering is a n x n square (2<=n<=100) array. The castle (the initial place of Prince) is on the first row and first column. Each day, the Prince could go as far as possible, as long as the destination trip is on the same row or on the same column as he is now and everyday he must move out from his current place. The Prince also can stay on the castle while on his trip but the same rule applies, he must move out the following day. The Prince then goes happily in the trip with promise that he will already in the castle on the k-th day.But suddenly, on the p-th day, the castle is being attacked and the Queen sends message to the Prince to return the next day (that is, the (p+1)-th day). The Prince could be anywhere in the map, but the message gets to him instantly. Your task is to compute the probability of the Prince could come back to the castle in time. If the Prince is already in the castle on the p-th day, it's counted as a succeed possibility. The output should be an integer in the range 0 to 1000 (inclusive) as 1000 times of the probability, rounded down (so, 0 is impossible, 1000 is always possible)