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:
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.
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.
For each input, print the number of distinct strings that Shabnam will be able to print.