Description

Dora, a junior interior technician, must tile a long hallway that is 2 cells wide. The storeroom only has identical tiles of two shapes: 1x2 (laid horizontally) and 2x1 (standing vertically). When the hallway is n cells long, how many distinct ways are there to cover it completely with no gaps and no overlaps?

Input

Output

Constraints

• •1 <= n <= 45
• •Tiles may only be rotated; only the two shapes 1x2 and 2x1 are used

Examples

3

3

6

13