#!/usr/bin/perl

use warnings;

sub power
{
	my $n=shift;

	if($n==0)
	{
		return (1, 0, 0, 1);
	}
	elsif($n==1)
	{
		return @_;
	}
	elsif($n % 2)
	{
		my @x=power
			(
				($n-1)/2,
				$_[0]**2+$_[1]*$_[2],
				$_[1]*($_[0]+$_[3]),
				$_[2]*($_[0]+$_[3]),
				$_[1]*$_[2]+$_[3]**2
			);
		return
			(
				$x[0]*$_[0]+$x[1]*$_[2],
				$x[0]*$_[1]+$x[2]*$_[3],
				$x[2]*$_[0]+$x[3]*$_[2],
				$x[2]*$_[1]+$x[3]*$_[3]
			);
	}
	else
	{
		return power
			(
				$n/2,
				$_[0]**2+$_[1]*$_[2],
				$_[1]*($_[0]+$_[3]),
				$_[2]*($_[0]+$_[3]),
				$_[1]*$_[2]+$_[3]**2
			);
	}
}

my $f=(power(shift, 0, 1, 1, 1))[1];
print "$f\n";