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).
Автор задачи: Mugurel Ionut Andreica
Источник задачи: Romanian Open Contest, December 2001