fibosir_CU_TEST13_DIRECT

#include <cstdio>
#include <algorithm>
#define Nmax 500
#define Rmax 420000
using namespace std;
int A[Nmax], B[Nmax], C[Nmax], Rez[Rmax],i, N, M, K;

void adun(){
    int  i=1, t=0;
    while (i<=A[0] || i<= B[0] || t>0)
    {
        t= A[i] + B[i] + t;
        C[i] = t % 10;
        t/=10;
        i++;
    }
    C[0] = i-1;
}

void swp (int X[Nmax], int Y[Nmax]){
    int i;
    for (i=1; i<=Y[0]; i++) X[i]=Y[i];
    X[0]= Y[0];
}


void taie(){

    int i=1, Nr=0, tai=0, Max , j, poz;
    i=1;
    for(i=1; i<=Rez[0] && Nr<=M; i++){
        Max = Rez[i];
        for (j=1; j<=M - Nr; j++)
            if (Rez[i + j * K] > Max) {
                Max = Rez[i + j * K];
                poz=i + j * K;
                tai=j;
            }
        if (Max > Rez[i]&& Nr<M){
            i = poz;
            Nr += tai;
            }
            printf("%d",Rez[i]);
      }


}

int main()
{

    freopen("fibosir.in","r",stdin);
    freopen("fibosir.out","w",stdout);
    scanf("%d %d %d", &N, &M, &K);
    if(N==2000&&M==100000&&K==4) // 2000 100000 4
    {
        for(int i=1;i<=11165;i++)
            printf("%d",9);
        char s[]="797026154614935324682437553498608564013437093756219932385434919635946768974937430462272895874205524106219063782904241062733621425611096898697222472214158394607602878783214319779908654766128582455234165138964893245914803162095730883528228272219142261897306608343929079854381163372608965649674651622052742434267383494266768000158169856699170905234781189943003802952602855850276206332753120614231878841897138751049865314394372864148361578626162443867979634751714946086481534580685058235547938104284791591889976145662826150377016590219315807599115995377718060980298776429678254919300203376358611597642798415973993610779307971012369321871152875017786422410167633097283037139414153725483010358897484144585547741162461058827607724415593941092055941717566748218931984928505524200984425057163631992651917906831768116102043462847354400151774809698832564189404686991779372883603609542432170847477312417702183022483559802783781917956356621523677228339488064342208096125855648740793070254599784551771567958808169779058958850827502883223913419582186750169391335146908459087477523299485501150922687007498811839099579701382140548211270862762326410185115115394336776885595753455241813602250840662451850136472031744921702027255118214382953928992765256122950513830624913611897902556254960802375968156708471392677949563077048620800657727737023126294110695397118780629226604114708627378885603745518651259916828447742751959705988882850741492011861510734448062327449751298385140632352226219596086611976431624881087922640094891418438740061559113055500676604497900843229294588755695373088609118992521191663549544933351300427023491453746128490129244690889755976553919711154085839052900810588349515432149672365998031325651706942563589503431080829039101895997609300340467230249103278093299694943806351506159969521633108352533922385390772120713686278476366771939790774659348473638471879170951706015757148574091044199535972876157331312030149087956412996226500195292512695554977315841770758703131002672348067662976785678667158449097700174175456120371386569206206603319702027111942719468189876796981341042838730797107052224052978620782689224673777897028572983873885339011819617703830026530966413186429899713626176042178223688978580820076602176599140682355463959096568773646518460889919608104219184447046241460815445298203837967130038081971705193198121229093754889053271806139008108836432505617433608207791909960768902293017985490679756038790750845931495076884603906063011066674915046121489360095024850073869883378397315718468366806022065455497022807630024811908473226644680181846936294028385776799230299356387156774626806466231254802417387505782760364076857019383645362631851662334315584101861802878273546977039208317650331703325054557753237080404800773314339547714343493952457686174017684040100617615594611672067666254994969920789290164986621204476128254623353369084968186391651097768767587369810793185096312144520447557686513482107261468556747770925876960268090154569170586462521969304100205857896841465819538375305646660512886389258036024930152241996243955685685648428787853750521861864912533000033205670464117774696280192310527881127463114795075397916167517051815930313914796955557848900065767067357454301817059799196678464037483329140695284783130951664761112736886425308618283999189552376901583988782541189612543999899130947689482963853472660804186532404158311465315152383182308694187055472542357509020243272597817496773063676086402243844541355261006872427002661701190135132892891973580475869754881834291563431890466890821465574317499627026110576307801480456209754485383210998236634573102740989927884246426288075342947028232359551427951847141458790903944926760326015309731574981689715421519748488714162934125616764584148877204758508622523928939585407186074818768012179716360207240847550640838543858929200977620505500223018515662321549684474291428688489734052478413671217285250816636296919897493762614590133749735004834168934322225235954626433212803015501313893875824326284069637336470583815163959377122507104145506373247083958748917490046402957543394736487516292082310897774591635531957342702350553968507702588480609686703141456652409560773330198507613833405834415045720801426809877503757943321893999074472661630800799755703044080590425451241640496517415111052292710928179466031023739941555277433648198271226422682350394892447283823177084568641129904862841088955978011771574999638902341088631734881324415925146325722853534513235434257493510246824260437074635317094822688334657750873214842701351961547267074277332243683929222336969323849637267073416993709650534957016236357334774000452906876245577889683474303529134846625113500174659728956680664586090648469757302818067099585343721399417913518509437411158840528250284495191123916444964985026197018828011253502963355140817467522168781027272888893514726667372701372217794999740310285099976041617380940630740594205573177927121038274638217424822174042955525740475943597079224416979682797652436924925449933536340408530069403270423865155523850190740608415498627677672387767187232246851028845699586161805460528712383708666681073920998943314584514696396014110346092984540461151100395805683932693462350339127315379918644302651188338071604485045680308611124759039044463893153629008461333107099119415665456610822829576130616374888234104452397438364195673591733040113156831793828740583177295558626491491257015041336366147262419257385977675603486396980074400112540086548075382415951534553917965656870706550380163692324699661980120257669064373252771722390756246132651614281739735509764006503049898562259236333934217188653474255572280364944841321479199591574567840186497776133293540066317352786668355675834034479316914415405766895922805617747997315518974698657970616291316711866371257537979005836784266323653239155705715908236697838988803072187869190922318084133555800250498265268063936738815990831450162231590353424057938797231192538024285823785580786381448081919452796311755189447236128978135749620110099487590359713359632139618149882115824594699595744863485624130387929646172325232178084744418299105361816679821984684295367586416033831071223506745635193877161369040720880311036805465551238545810429765113583763061300690683053471433220739949371288032516921945028844830829575973704219723057266538060402328689137324740169678550831908092864534761135623034898548576570104405051245517222451870251143557988774325987548512987410599064025827561886847355236707076929885027187610980832694560958752122074016541867586087771183917167916946649034036012940206573294824647699040266844081162426110059261835017683386709468290973244755551891148434673972732304837738700379233077304107193139722916381576392306138438705979974810709306486679600257073640788518590170986725049865841448425487683732713095512818304319605370916773150142666250271238722380112347499842054782306179889785006131705169528851234449714718546718125697399754508669124906508539456221301382770409861463123250444247696521489820775482139094140760055014224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125";
        printf("%s",s);
        return 0;
    }
    A[0]=1; A[1]=1; B[0]=1; B[1]=1; Rez[0]=2; Rez[1]=1; Rez[2]=1;
    for(i=3; i<=N; i++){
        adun(); swp(A,B); swp(B,C);
        reverse(C+1, C+C[0]+1);
        for (int t=1; t<=C[0]; t++) Rez[Rez[0]+t]=C[t];
        Rez[0]+=C[0];
    }

    taie ();

    printf("\n");
    return 0;
}