Mondrian's Tiling Dream

Dutch painter Piet Mondrian was fascinated by squares and rectangles. After finishing his infamous "Toilet Series" paintings (created with toilet paper after he ran out of canvas), he dreamed of filling a large rectangle with small rectangles of dimensions $$2$$ (width) and $$1$$ (height) in various ways. As an expert in this domain, he quickly realized that only a computer could enumerate all the different tiling methods. Help him calculate the number of ways to tile the large rectangle, so that his dream doesn't turn into a nightmare!

The small rectangles (tiles) can be placed either horizontally or vertically to completely fill a 2xn rectangle without overlapping.

inputFormat

The input consists of a single integer n (where n ≥ 1), representing the length of the large rectangle. The large rectangle has a fixed height of 2 and a variable width n, forming a 2xn board.

outputFormat

Output a single integer representing the number of ways to completely fill the 2xn rectangle using 2x1 tiles. Tiles can be placed either horizontally or vertically.

sample

1

1