Brain Pleased

Like most of the other teenage girls, Shabnam loves to generate strings. But recently, she discovered that almost all the keys in her keyboard are dysfunctional. The only two keys that are working are 'a' and space. But for the love of strings, Shabnam decided to write all possible strings with this broken keyboard.

While writing the strings, Shabnam will follow these rules:

1. She will only write strings that will not include any leading and trailing spaces.
2. There will be only one space between two separate words. A word here is a string of 'a''s.

Given N, you have to say how many distinct strings Shabnam will be able to write. Two strings will be distinct if they have different characters in at least one position.

Input

The first line contains a sigle integer N, the length of the string.

For 10 marks, N is not more than 3.

For 20 marks, N is not more than 10.

For 70 marks, N is not more than 50.

Output

For each input, print the number of distinct strings that Shabnam will be able to print.

Sample

1

1