The young botanist Vanya decided to grow house plants in his apartment. He bought N tubs with orange trees. Unfortunately, in the summer all his trees became infected with spider mites, which ate away all the leaves. Vanya was very upset. The next day he bought an insecticide and sprayed the trees with it. The mites were killed and new leaves grew on the trees.

After that Vanya opened his botany encyclopedia and read that it was not that easy to deal with spider mites. Even if all the mites on a plant died, there still remained their eggs in the soil, and new vermin would grow from these eggs in a certain period of time. To fight spider mites, the encyclopedia recommended to fix a permutation P and rearrange the tubs with plants according to the rule P after each spraying. It was claimed that all eggs would die as soon as all the tubs were returned to their original places for the first time.

Vanya decided to calculate how many times he would need to spray the trees. Let N = 5 and P = (4, 1, 5, 2, 3). Denote the initial arrangement of the tubs with orange trees by 1, 2, 3, 4, 5. Then the tubs will occupy the following places:

• after the first spraying: 2, 4, 5, 1, 3;
• after the second spraying: 4, 1, 3, 2, 5;
• after the third spraying: 1, 2, 5, 4, 3;
• after the fourth spraying: 2, 4, 3, 1, 5;
• after the fifth spraying: 4, 1, 5, 2, 3;
• after the sixth spraying: 1, 2, 3, 4, 5.

In this example, all spider mite eggs will be killed after six sprayings.

Assuming that all possible permutations of an N-element set are equiprobable, you must determine the average number of sprayings needed to kill all eggs.

You are given the number N of orange trees (1 ≤ N ≤ 50).

Calculate the average number of sprayings necessary for the total extermination of spider mites and their eggs, and output the integer part of this number.

In the sample there exist two permutations of orange trees: (1, 2) and (2, 1). If the first permutation is chosen, then the mites will die immediately after the first spraying; in the case of the second permutation, the mites will die after the second spraying. Thus, the average number of sprayings is 1.5.