protection2

#include <bits/stdc++.h>
#define P 1000003
using namespace std;

int A1[] = {1, 544459,511030,593582,458305,332975,240615,653307,366649,
848024,869425,85989,586974,953515,174828,603107,6077,123323,707130,117424,
500779,20745,316792,114260,416176,352526,418531,439629,716096,205491,522310,
458479,44783,56878,420187,385716,116536,35760,575044,806649,984273,984695,
836769,380988,641085,875885,17840,915484,413954,301750,662628,144797,312312,
43338,518574,403468,877242,823586,588063,346912,486925,924947,19227,550670,
510032,104939,184665,14012,440350,586113,976282,207913,100941,369176,468184,
897360,326810,267838,941731,379427,94101,626782,771267,352052,214010,565569,
461852,249576,800200,305617,218134,39484,471473,974519,280973,77687,418017,
331789,431178,80705,167742};

int A2[] = {1, 657221,261658,387252,737134,326779,889623,663858,52903,573411,
756962,363964,277757,94576,372746,96314,281457,253922,424711,307864,660123,585323,
698892,464127,6618,622778,497023,657790,622117,604930,708789,135608,130525,444626,
145469,750784,421412,973780,854514,283592,957863,384048,960447,593872,644272,78591,
827903,878473,471462,798591,871460,996396,749457,125889,778059,876350,690859,401096,
933449,344439,417543,400069,639190,431853,846552,928272,649659,351410,125974,966117,
383569,379602,455586,493005,635430,324855,807119,869969,310423,883099,401085,344762,
330240,243918,31063,855243,387983,355821,336506,50229,222837,292253,244089,256619,
979647,646485,826009,404200,211398,111130,308332};

int A3[] = {1, 93855,829113,876522,782857,190273,806570,656169,355976,765869,597897,
590157,770072,624117,207241,150232,941296,142066,166956,908300,687356,735045,936428,
318264,500411,137809,493034,892815,374947,861720,322698,348994,622082,356053,727552,
93414,435329,364686,621477,952284,169813,540660,863483,442585,708555,452568,958431,
583494,821763,891083,636770,68320,444062,139468,620542,752004,27947,512783,446427,
289331,594998,803360,313554,81183,899141,494223,689503,327775,411694,406845,10964,
465375,744535,133906,27801,179685,155688,982276,278220,15471,586197,432365,120750,
520325,696948,131804,533403,336840,962649,650257,982353,382583,650146,93711,986179,
564841,357856,279110,329910,610713,435807};

int main()
{
    int k, a1, a2, a3, b1, b2, b3, i, n;
    ifstream fin("protection.in");
    ofstream fout("protection.out");
    fin >> n;
    if (n == 1)
    {
        fout << "9\n";
        fout.close();
        return 0;
    }
    k = 0;
    while (20000000*k < n) k++;
    if (20000000*k > n) k--;

    a1 = A1[k];
    a2 = A2[k];
    a3 = A3[k];
    if (k == 0) i = 2;
    else i = 20000000 * k + 1;
    for ( ; i <= n; i++)
    {
        b1 = (2 * a2 + a3) % P;
        b2 = (2 * a1 + 2 * a2 + a3) % P;
        b3 = (4 * a1 + 4 * a2) % P;
        a1 = b1;
        a2 = b2;
        a3 = b3;
    }
    i = (4 * a1 + 4 * a2 + a3) % P;
    fout << i << "\n";
    fout.close();
    return 0;
}