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.
First line of input as an integer N.
Print an integer being the result of the test.
Sample Input 0
Sample Output 0
In the first example, first two roads are sufficient for connecting the cities so the answer would be 2.
Sample Input 1
Sample Output 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/20*4 + 16/20*3 = 3.2 and since you have to print only the integer part as output, print 3