const int SZ = 2;
struct Matrix{
    int mat[SZ][SZ] = {};
    
    Matrix(){}
    void makeUnit(){
        memset(mat, false, sizeof(mat));
        for (int i = 0; i < SZ; i++)
            mat[i][i] = 1;
    }
};

Matrix operator * (Matrix a, Matrix b){
    Matrix answer;
    for (int i = 0; i < SZ; i++) // hang cua a
        for (int j = 0; j < SZ; j++) // cot cua b
            for (int k = 0; k < SZ; k++) // bien chay 0 -> SZ-1
                ans.mat[i][j] += 1ll * a.mat[i][k] * b.mat[k][j],
                ans.mat[i][j] %= MOD;
    return answer;
}

Matrix power(Matrix a, long long n){
    if (n == 1) return a;
    Matrix answer = power(a, n / 2);
    answer = answer * answer;
    if (n % 2 == 1) answer = answer * a;
    return answer;
}

// Matrix power(Matrix a, long long n){
//     Matrix answer; answer.makeUnit();
//     while (n > 0){
//         if (n & 1)
//             answer = answer * a;
//         a = a * a, n >>= 1;
//     }
//     return answer;
// }

main(){
    int n; cin >> n;
    Matrix base; base.mat[0][0] = 0, base[0][1] = 1; // [f(0) f(1)]
    Matrix mul;
    mul.mat[0][0] = 0; mul.mat[0][1] = 1;
    mul.mat[1][0] = 1; mul.mat[1][1] = 1;
    
    Matrix answer = base * power(mul, n-1);
    cout << answer.mat[0][1];
}