$n=<>;
($a,$b,$c,$d)=(
	1, 0,
	0, 1
);
for(reverse 0..30){
	($a,$b,$c,$d)=(
		($a*$a+$b*$c)%1000, ($a*$b+$b*$d)%1000,
		($a*$c+$c*$d)%1000, ($b*$c+$d*$d)%1000
	);
	if($n>>$_&1){
		($a,$b,$c,$d)=(
			$c,               $d,
			(2*$a+2*$c)%1000, (2*$b+2*$d)%1000
		)
	}
}
print+(2*$a+2*$b+$n%2-1)%1000