Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Brain Pleased

By TarifEzaz · Limits 1s, 512 MB

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

InputOutput
1

1

Discussion

Statistics


40% Solution Ratio

BRACU_1isPrimeEarliest, 3M ago

BRACU_1isPrimeFastest, 0.0s

BRACU_1isPrimeLightest, 131 kB

bracu_abcShortest, 289B

Submit

Login to submit