Henry Shaker works as a barman in the favorite pub of Vito Maretti. Every evening he pleases the gangster with a new cocktail: vodka and Martini, gin and orange juice, kefir and mineral water. Vito pays generously for each new cocktail, but if the barman repeats a cocktail he is in trouble: Vito may shoot him. So Henry wants to know how soon he will have to leave the town. In order to know this you are to count how many different cocktails he can make having N components. A cocktail is the mixture of two or more components. Unfortunately, Henry can’t use one component more than once in the same cocktail. Nevertheless 'vodka and Martini' and 'Martini and vodka' are two different cocktails.
The first input line contains an integer N (1 ≤ N ≤ 21) — an amount of components.
an integer number of possible cocktails.
Problem Author: Sergey Pupyrev
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)