Given an \(2\) by \(N\) grid, determine the total number of distinct ways to completely cover the grid using \(1\) by \(2\) dominoes. Each domino can be placed either horizontally or vertically, and no dominoes can overlap or extend beyond the boundaries of the grid.

Constraints

\(1 \le N \le 30\)

Input Specification

The first line of input contains one integer, \(N\), the width of the grid.

Output Specification

Output the number of ways to tile the grid.

Sample Input

4

Sample Output

5

Explanation

One possible way to tile the grid is this: