/* Dasproc C - 2019
William Handi Wijaya
0087

Program untuk menghitung berapa kali fungsi
rekursi dipanggil..
*/

#include <stdio.h>

void rekursi(int x, int *counter, int temp);

int main(void)
{
    int x;
    int counter = 0;
    int temp = 0;
    scanf("%d", &x);
    rekursi(x, &counter, temp);
    counter %= 1000001;
    printf("%d\n", counter);
    return 0;
}

void rekursi(int x, int *counter, int temp)
{
    temp = *counter;
    temp++;
    *counter = temp;
    if (x <= 0)
    {
        return;
    }
    rekursi(x - 1, counter, temp);
    rekursi(x - 2, counter, temp);
    rekursi(x / 2, counter, temp);
    rekursi(x / 3, counter, temp);
    return;
}