Zoo

Time limit

Memory limit

128 MB

Problem

A zoo has cages arranged as a grid with 2 columns and N rows. Each cell can contain at most one lion.

When placing lions, no two lions may be in horizontally or vertically adjacent cells.

Find the number of ways to place lions in the 2*N cells while satisfying this condition. The arrangement with no lions is also counted as one valid way.

Input

The first line contains the number of rows N.

1 <= N <= 100,000

Output

Print the number of valid lion placements modulo 9901.