DSA Week 2

Explosive containers

All containers in the world are divided into two categories - with or without trotyl (TNT). Only a fool would put a box with TNT on another box with TNT. Since you are not a fool (hmm ...), you know exactly that TNT explode, especially if it is on another box with TNT. You are in the room in which there are two types of boxes in a huge quantity. Suddenly, the lifter comes into the room from the hatch. It fails. It is intended to build a tower with n boxes. In order to estimate your chance to survive, you have to count the number of outcomes where nothing explodes.

By the way, what a reasonable person like you doing in a room with a bunch of TNT?


One integer n (1n < 45).


Print the number of good outcomes.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1
Input example #2
Output example #2