#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int mod = ;

int t;

long long print,sum;

struct node

{

    int n, m;

    long long a[][];

    node()

    {

        memset(a, , sizeof(a));

        n = ;

        m = ;

    }

}s,p,ans;

node mul(node a, node b)

{

    node c;

    c.n = a.n;

    c.m = b.m;

    for (int i = ; i < a.n; i++)

        for (int j = ; j < b.m; j++)

            for (int k = ; k < a.m; k++)

            {

                c.a[i][j] += (a.a[i][k] * b.a[k][j]) % mod;

                c.a[i][j] %= mod;

            }

    return c;

}

node qpow(node a, int b)

{

    node t;

    t.n = ;

    t.m = ;

    for (int i = ; i < ; i++)

        t.a[i][i] = ;

    while (b)

    {

        if (b & )

            t = mul(t, a);

        a = mul(a, a);

        b >>= ;

    }

    return t;

}

int main()

{

    scanf("%d", &t);

    s.n = ;

    s.m = ;

    s.a[][] = ;

    p.n = ;

    p.m = ;

    for (int i = ; i <= ; i++)

    {

        p.a[i][] = ;

        p.a[i - ][i] = ;

    }

    p.a[][] = ;

    ans = mul(s, qpow(p, t - ));

    for (int i = ; i <= ; i++)

        sum = (sum + ans.a[][i]) % mod;

    printf("%lld\n", sum);

    return ;

}