题目描述

X 星球上的一种病毒正在快速传播，许多生物体的 DNA 被感染。经过数周的研究，X 星球的 CHO（生物健康组织）终于发现该病毒的 DNA 特征非常简单，仅有两种形式：

101

111

不幸的是，X 星球上的生物 DNA 也都是由 $0$ 和 $1$ 构成的二进制串。如果某个生物体的 DNA 中包含 101 或 111 作为子串，则认为其已被感染；否则未感染。

现在给出一个整数 $L$，表示 DNA 串的长度。则一共有 $2^L$ 个不同的 DNA 串。你的任务是求出其中有多少个未被感染的 DNA 串（即不包含 101 和 111 作为子串的串）。

由于结果可能很大，你只需输出答案对 $2005$ 取模的结果。

输入格式

输入包含多个测试用例，每个用例为一个正整数 $L$，表示 DNA 串的长度：

$1 \leq L \leq 10^8$

输入以 文件结束（EOF） 方式结束。

输出格式

对于每个测试用例，输出一行，表示未被感染的 DNA 串数量对 $2005$ 取模的值。

4

9