On the Day of the Flag of Russia a shop-owner decided to decorate the show-window of his shop with textile stripes of white, blue and red colors. He wants to satisfy the following conditions:

- Stripes of the same color cannot be placed next to each other.
- A blue stripe must always be placed between a white and a red or between a red and a white one.

Determine the number of the ways to fulfill his wish.

**Example.** For *N* = 3 result is following:

### Input

*N*, the number of the stripes, 1 ≤ *N* ≤ 45.

### Output

*M*, the number of the ways to decorate the shop-window.

### Samples

**Problem Source: **2002-2003 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 2002