Jack Ma’s New Hobby

Problem Statement:

Sitting in a Chinese prison for a misunderstanding, Jack Ma developed a hobby of dominoes art. While putting together, arguably the best domino art the prison had seen, he began to wonder… What if I had an infinite supply of 1 × 2 and 2 × 1 dominoes and had to fill an N × 2 grid? For example, Jack can fill a 2 × 2 grid using 2 1 × 2 dominoes or 2 2 × 1 dominoes. Find the total number of ways Jack can fill an N × 2 grid using only 1 × 2 and 2 × 1 dominoes.

Constraints:

Subtask 1: 10 points

• 1 ≤ N ≤ 5

Subtask 1: 10 points

• 1 ≤ N ≤ 15

Subtask 1: 10 points

• 1 ≤ N ≤ 10⁵

Input Format:

• The first line contains a single integer N

Output Format:

• Print a single line containing the required answer

Sample input:

3 

Sample output:

3