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

Ural Championship 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Tram Solitaire

Time limit: 0.5 second
Memory limit: 64 MB
It might seem that a traffic jam is not a problem for trams. However, if tram rails are laid on the roadway, a tram is on equal terms with other vehicles. In fact, a traffic jam is a greater problem for trams because they can't drive around the difficult section of the road.
Tram driver Zina can always find what to do while her car is stuck in a traffic jam. She likes most to play a solitaire, in which a deck consisting of cards of two suits (hearts and spades) is used. In each suit, there are n cards of different values (so, there are 2n cards in total). Zina takes cards from the deck one by one and puts them down in a row from left to right face up. After putting down each card, Zina performs sifting: if there are two cards of the same suit or of the same value separated by exactly one card, then the leftmost of these cards is removed, and all the cards that are to the right of it are shifted to the left by one place. If there are several such pairs, then the pair is chosen that is nearer to the beginning of the row. Sifting can be performed many times, as long as there are such pairs in the row. Zina wins the game if after dealing the whole deck and sifting there are only two cards in the row.
For example, if at some moment there were the cards “H7 S5 S2 H4” in the row (“H” denotes hearts and “S” denotes spades), and the card “S7” was added, then after the first sifting we get “H7 S5 H4 S7.” Then the first of the two pairs is “sifted,” and the cards “S5 H4 S7” are left. Finally, after sifting, we get “H4 S7.”
Zina has always wanted to know the chances of winning the game. Can you help her?


The only input line contains the integer n, 2 ≤ n ≤ 10000.


Output the probability of winning the game, in the form of an irreducible fraction. Use the format given in the sample.


Problem Author: Vladimir Yakovlev
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008
To submit the solution for this problem go to the Problem set: 1615. Tram Solitaire