ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Junior Contest October'2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Cocktails

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

The first input line contains an integer N (1 ≤ N ≤ 21) — an amount of components.

Output

an integer number of possible cocktails.

Sample

inputoutput
3
12
Problem Author: Sergey Pupyrev
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)
To submit the solution for this problem go to the Problem set: 1402. Cocktails