Patrick Lin (The Ultimate Overlord of WLMAC) recently hired Patrick Bian to be part of the Project Metropolis team. Since this school isn't big enough for two Patricks, on St. Patrick's day, the two will engage in the ultimate battle of the Patricks to determine which is the one true Patrick.
The battle consists of multiple rounds in which they will play best of rounds, meaning the first person to win rounds will win the tournament. In each round, there is always a winner and a loser. This means they will always play at most rounds.
Patrick Lin really wants to win this battle so he will try to list all the possible sequences of outcomes in which he wins the battle. Given an odd integer , how many different sequences of wins and losses are possible such that Patrick Lin wins the tournament?
Note: you will require 64-bit integers to solve this problem (e.g. long
in Java or long long
in C++).
Input Specification
A single odd integer .
Output Specification
The number of different sequences of wins and losses are possible such that Patrick Lin wins the tournament.
Sample Input 1
3
Output for Sample Input 1
3
Explanation for Sample Case 1
Here are all the possible sequences of rounds in which Patrick Lin wins the tournement (W
denotes a round where Patrick Lin wins, and L
denotes a round where Patrick Lin loses):
WW
WLW
LWW
Sample Input 2
9
Output for Sample Input 1
126
Comments