#include<iostream>

using namespace std;

int a,b,c,d,e,f,g,h;
a=1;
b=1;
c=1;
d=0;
e=1;
f=1;
g=1;
h=0;

int p2(int n)
{
    int ae=0;
    res=
    while(n>0)
    {
        if(n%2==1)
            res=res*a;
        a=a*a;
        n=n/2;
    }
    return res;
}

int main()
{
     int n;
     cin >> n;
     cout << fib(n)%123456789;
}