PKU 2440(DNA) 번역

시간 제한 1초

메모리 제한 65536K

문제 설명

어떤 바이러스가 행성 X를 공격하여 수많은 생명체가 감염되었다. 몇 주 동안의 연구 끝에 CHO(Creature Healthy Organization)은 이 바이러스는 101과 111 두 가지의 간단한 DNA로 구성되어 있음을 발견했다. 불행히도, 행성의 생명체들도 0과 1로 구성된 DNA를 가진다. 만약 생명체의 DNA가 바이러스의 DNA를 포함하면, 그 생명체는 감염당할 것이다. 포함하지 않으면 감염되지 않는다. 정수 L이 주어졌을 때, DNA의 길이가 L인 2^L개의 생명체 중 감염당하지 않는 생명체의 수를 구하여라.

입력

정수 L(1<=L<=10^8)이 여러개 주어진다.

출력

감염당하지 않는 생명체의 수를 2005로 나눈 나머지를 출력한다.

입력 예제

4

출력 예제

9

http://poj.org/problem?id=2440