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
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