We have a country containing _N _cities. Each day we choose 2 cities such that there is no road between them and build a road between them. We choose each pair of nonadjacent cities with equal probability. Let X be the number of days before we obtain a connected country. What is the expected value of X? Output the integer part of answer.

Input Format

First line of input as an integer N.

Constraints

$N<=30$

Output Format

Print an integer being the result of the test.

Sample Input 0
3

Sample Output 0
2

Explanation 0

In the first example, first two roads are sufficient for connecting the cities so the answer would be 2.

Sample Input 1
4

Sample Output 1
3

Explanation 1

In the second example if the first three roads of the country are edges of a triangle, then we need a fourth road to make the country connected, otherwise the country would be connected with first three roads. The probability of the former situation is 4/20 (number of triple of roads that make a triangle divided by number of ways we can choose 3 different roads), and the probability of later situation is 16/20. So the result would be 4/204 + 16/203 = 3.2 and since you have to print only the integer part as output, print 3

见题面

见题面