#include <fstream>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

int dp[3000014];

int main()
{
    int n;
    cin>>n;
    dp[1]=1;
    dp[2]=1;
    if (n<=1000000){
        for (int i=3; i<=n; i++){
            dp[i]=((dp[i-1]%666013)+(dp[i-2]%666013))%666013;
        }
        cout<<dp[n];
    }
    else{
        int x;
        for (int i=3; i<=4*666013; i++){
            dp[i]=((dp[i-1]%666013)+(dp[i-2]%666013))%666013;
            if (dp[i-1]==1 && dp[i]==1){
                x=i-1;
                break;
            }
        }
        cout<<dp[n%x+2];
    }
    return 0;
}