Zoo

Interview

Time limit2sMemory limit128 MB

Summary

Count the ways to place non-attacking lions in a 2 by N grid so that no two lions sit in adjacent cells, modulo 9901.

Level: Medium4 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

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.

Examples1

Example 1
Input
```
4
```
Expected output
```
41
```