ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Romanian Open Contest December 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Ship Routes

Time limit: 1.0 second
Memory limit: 16 MB
A Romanian tourist went on a trip to the Mediterranean Sea. He arrived to one of the cities of the 3 islands he is going to visit. Every island has exactly N cities and they are all ports. The tourist plans to begin his journey from the city he is in, visit all the other 3*N-1 cities exactly once and then return to the starting city so he may go back home after that.
Unfortunately, there are cannibals along the roads on all the 3 islands. That's why travelling on the road between 2 cities on the same island is very dangerous and, consequently, prohibited. Hopefully, there are always ship routes. Every pair of cities which are not on the same island is connected by such a ship route. There are no routes between cities which are on the same island.
The tourist wants to know in how many ways he can plan his journey through the 3 islands.


The input contains a single number: N (1 ≤ N ≤ 30), the number of cities on each of the 3 islands.


You should output a single number: the number of ways the tourist can plan his trip. Note that 2 trips are identical if the successions of the 3*N cities are identical or if the succession of the 3*N cities of the first trip is the same as the succession of the 3*N cities of the 2nd trip, read backwards (for instance, if every island had 1 city, numbered according to the island's number, the trips 1-2-3-1 and 1-3-2-1 would be identical).


Problem Author: Mugurel Ionut Andreica
Problem Source: Romanian Open Contest, December 2001
To submit the solution for this problem go to the Problem set: 1172. Ship Routes