Tiling the 2×N Canvas with Dominoes and L‐Trominoes

Little Ming is fascinated by building block art. He has two types of blocks:

• An I-shaped block covering an area of 2 units (i.e. a domino), and
• An L-shaped block covering an area of 3 units (i.e. an L‐tromino).

He has a canvas of size 2×N, which can be viewed as 2×N grid of 1×1 cells. The task is to completely tile the canvas using these two kinds of blocks. The blocks can be rotated arbitrarily, but the canvas orientation is fixed. Note that since the area of the canvas is 2N, and the L‐block has odd area (3), an L‐block must be used in pairs (i.e. an even number of L‐blocks) for a valid tiling.

It turns out that the number of tilings f(n) satisfies the recurrence relation \[ f(n) = f(n-1) + f(n-2) + 2f(n-3),\] with the initial conditions \[ f(0)=1,\] \[ f(1)=1,\] \[ f(2)=2.\]

Given an integer N, output the total number of distinct tilings.

inputFormat

The input consists of a single integer N (0 ≤ N ≤ 10⁵), which represents the number of columns of the 2×N canvas.

outputFormat

Output a single integer which is the number of ways to tile the 2×N canvas using the given blocks.

sample

1

1