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. 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?

Input

One integer $n(1\le n<45)$.

Output

Print the number of good outcomes.

Examples