동물원

어떤 동물원에는 가로 2칸, 세로 N칸으로 이루어진 우리가 있다. 각 칸에는 사자를 최대 한 마리 넣을 수 있다.

사자를 배치할 때는 서로 가로 또는 세로로 인접한 두 칸에 동시에 사자가 있어서는 안 된다.

이 조건을 만족하도록 2*N개의 칸에 사자를 배치하는 경우의 수를 구하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우로 센다.

첫째 줄에 우리의 세로 크기 N이 주어진다.

• 1 <= N <= 100,000

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력한다.