Baekjoon 10826 피보나치 수 4 JAVA

10826번: 피보나치 수 4

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

풀이

피보나치의 10000번째 값은 어마어마하게 큰 수 이다.

3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551363373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386465273130008883026923567361313511757929743785441375213052050434770160226475831890652789085515436615958298727968298751063120057542878345321551510387081829896979161312785626503319548714021428753269818796204693609787990035096230229102636813149319527563022783762844154036058440257211433496118002309120828704608892396232883546150577658327125254609359112820392528539343462090424524892940390170623388899108584106518317336043747073790855263176432573399371287193758774689747992630583706574283016163740896917842637862421283525811282051637029808933209990570792006436742620238978311147005407499845925036063356093388383192338678305613643535189213327973290813373264265263398976392272340788292817795358057099369104917547080893184105614632233821746563732124822638309210329770164805472624384237486241145309381220656491403275108664339451751216152654536133311131404243685480510676584349352383695965342807176877532834823434555736671973139274627362910821067928078471803532913117677892465908993863545932789452377767440619224033763867400402133034329749690202832814593341882681768389307200363479562311710310129195316979460763273758925353077255237594378843450406771555577905645044301664011946258097221672975861502696844314695203461493229110597067624326851599283470989128470674086200858713501626031207190317208609408129832158107728207635318662461127824553720853236530577595643007251774431505153960090516860322034916322264088524885243315805153484962243484829938090507048348244932745373262456775587908918719080366205800959474315005240253270974699531877072437682590741993963226598414749819360928522394503970716544315642132815768890805878318340491743455627052022356484649519611246026831397097506938264870661326450766507461151267752274862159864253071129844118262266105716351506926002986170494542504749137811515413994155067125627119713325276363193960690289565028826860836224108205056243070179497617112123306607331005994736687554438373113565281338734260993750380135389184554695967026247715841208582865622349017083051547938960541173822675978026317384359584751116241439174702642959169925586334117906063048089793531476108466259072759367899150677960088306597966641965824937721800381441158841042480997984696487375337180028163763317781927941101369262750979509800713596718023814710669912644214775254478587674568963808002962265133111359929762726679441400101575800043510777465935805362502461707918059226414679005690752321895868142367849593880756423483754386342639635970733756260098962462668746112041739819404875062443709868654315626847186195620146126642232711815040367018825205314845875817193533529827837800351902529239517836689467661917953884712441028463935449484614450778762529520961887597272889220768537396475869543159172434537193611263743926337313005896167248051737986306368115003088396749587102619524631352447499505204198305187168321623283859794627245919771454628218399695789223798912199431775469705216131081096559950638297261253848242007897109054754028438149611930465061866170122983288964352733750792786069444761853525144421077928045979904561298129423809156055033032338919609162236698759922782923191896688017718575555520994653320128446502371153715141749290913104897203455577507196645425232862022019506091483585223882711016708433051169942115775151255510251655931888164048344129557038825477521111577395780115868397072602565614824956460538700280331311861485399805397031555727529693399586079850381581446276433858828529535803424850845426446471681531001533180479567436396815653326152509571127480411928196022148849148284389124178520174507305538928717857923509417743383331506898239354421988805429332440371194867215543576548565499134519271098919802665184564927827827212957649240235507595558205647569365394873317659000206373126570643509709482649710038733517477713403319028105575667931789470024118803094604034362953471997461392274791549730356412633074230824051999996101549784667340458326852960388301120765629245998136251652347093963049734046445106365304163630823669242257761468288461791843224793434406079917883360676846711185597501880831379899970646053558729988579234456913330153760309328124858158886643077890113852386470615726945667558880086588624767580943752349815097022155951060156018129408784874658905396963956313602924001237254906679879809471957619197330842212632627921355525119616631887440832627430153939032280351825299229007692076240888798939515549385841668122331276855289688824358279031107436208700561040222904949633210734068658606065797923624038668264116422706612114355903400901494584198108172511200257135019189593506548956828047187523192158921192229072232798498512271663879541395466626440646538044663454161025433067126882513787935065641129706203676721313445591990277178134049404310097541436374176453594011552456586460882965780975476991412844518197827037828786682374410262550234752790038800074505508680024095330680981274950956673131203691423315191401850177192145018476457410307393510253429325142806254530857751919962363437924322157008507735682579889202655396479221723159022099010798301959490585059435080130444505038261678809930945405035722661899646949732635763759086069777883957301962272746297457228728336223004727693122736033466242926908756974382642657123131236376444913678755388474420131305321473456130993331954008455604660851763751750454850467878151332253493889963340143293183048656568151292085866865158358808113160657887591956465477036314540400904359558796041231860074818421176405741583679968456270120995710087617769910754709913863019881047539157982317414470122364342615946669853978417583483370309146236171017464319227085228248681556128114260167759687621214292825825820888717954634677969273174523686335523468194054233597386969802527075459442660427642365773817218037494425380539001962502840544063472386065750938776693235014525124121798836985522040388650691798677735797057038411786506188183573661656495295478988011986175414328934436509520339839235425929520708640442497383380897781639866830695667365051264668863042272531050342317167615353504411787242108418308555275868828220932465458131206241132903915938977652193209311796978699972437705337193195305263698305295438424056554952293822510391164267501567711329643761425215111035623459440901339926083035810805175700719979590602016570972471734113604023216986095116551079297106846368887941424539599860977511413902977489747717385272126053719535877861891628364008663827982500358871316251558502263310508632290877298573528934028220297865642607277118812785652152106936862185511355651902491567025344483848804089511515002396387950800426783652222085446250678302934572284541847667956233332592337625054426264551530481271472409528425518573764790372319301257164658238148274930227452766854751758029702784618625431940136061113261288506228856587043838840586795287891259711976223395354375744136526907552033321827124983633844043425636892221339645395819814377695478886406730823481137502145319822601401697483872692673182336574307669619881426207481682246485448470267375455687055026353211063594112394576821482276863882367557055208699626488294274889381279624571456330729525909793903014235121140554995606454008141777603748937580476179615397011221005116056656542746370246045729950888010874217292351024376126270202184028445851940414377747771007716846945489610254225317923175954758256171903902016493265288539890051212474203207453454625572536536045742987702249363224288353633316748887163954988805945316787463287606267960787282381225528445738412109747435377276788346353000702717397185918280244988399291377623228548869642917463678440436524673155645206675951616857357637769614954091721735743766019475360096916666332999662393156036287730027397661276611807468357794232046247708897431531529051712827681349692965496866143446064963434051589370826087350916599992758753959929494663015169179414709979255978670442359089705654694536837861475680842799611581714313434832326366214789216218908151551405930121885946003723150773644486263800312518227184201032811752639094887480160136916750251658559026744694447083270240826034823844695116973268616210576465319760392083622085812585907174325202085025878591610957769834614468647909923594024411748257606264981959859137357824815476665787498701114266432462448591823706652261429763625479341645429887727841312988180056342488802886637883309569997874270034823185618772306046490935594105494460069914662270267718505854480288918726874729859114812003717875603456710843496746855986932957512709005483352210792608436058928549903735514680910928378441274825847941966932665065237407038751125723516121460641350844923505219929054053644852185306475234707272751817932503932236091193203431892791290506540893869690472211842791857686076775158705814759658294146811718525839521917752581736614839398390261249093094528667953187883586765431826420068348988480491812457421793257337868436776409594901939281221861705810854504172934559625532952385770252053670279487124839951345420737409290522236889532071592548681739525503846297079436033702815026270743955493361250751871932480418283280067598385111100798078393110328390890500220165360990044030143976442234472285285522975776055479782385707334486014550785525780512905592055284217734247353718102945704582282891533053896599136984056767545822976598559064877152614961743824357492951592976955401338556033320015914358616033331429681125860395393049135896102281969781161992864083675395584576178136833840785600804247451883000522775151904290981260899597024752526731531466798808186856845864576585861948981449724498376176669494529609827089447742219117963444410606168551215038061118428665433713479022335701752253040618425933356497645086569582555544726393405646286883334088705585184183318368037999232565905015720025097128022598941317738071224212717445831383789386114806830529352880709932314018605144497520025619227754138211772649629731079206577767700069177146908434921214178422271560325131193739210585118913176737488710713388637898767837538855514938178173310212267829328892232730153979498289118046616616829619208738815371328328717629760282380537617156868898579181018248274895443323249322352906877875999710547549696133299266666325100323913315054322223682459069445655154969260354215456812504042140097173960202889467002983594225774005020869450077143260474000042365664810965077538947528823535499714683290515135006186045747942123918704942247170348401426244016915964058408463597917046982623083033105011293475494766545357838931705819961162141771602534515262533731261601971217564935361409840745306078523681555200268509328891300831586546117321898820442805960047826153093779326400650430022952071770119849961906039651452899953036982097977152687739570330941328893219907397622441975074623723951859477214382518502582987673072483172117841984391564603584656039172953378714787544693782073566238353539276301354306860082464725959132598411880379593062396828774094202294429404571072730982598874147520793219483669155059174960251938642113778852811113714586451495486143367003862361756691039251564490429479936113070620738794240891999108640714118327711635239236680449385513917591265276208119456233772847330971280713280077128451918492083600889181065129567411366825014103548735887256420620679794807812263583173402501935297713650025402649716154531770971446043430935469440733687697078144897920357334387868919166585291302562417729433998857172272812678468055467713582677339725990833680205432148221415751966135096700530557431580953953044541021030415272576077799927171590346281060010113394632994157288263066267703841436516592514581611793317651192941493254748093075080245739517071500926769019996820006688859399331049072030040487521517985770241363878918857753898180722764491106281918433216551485338678325667386389452716094704550781440164362788053803210144843998087272299952730644673650634686174711711934134053826235831716439669090578171365231773079639456298955507686178304439181575149808861474903747195685880372325470054892874524917686895839561606569566881675978788104009299229120889974589784614179675288415006390094627790799955945000527654088703472142597828262500554024694352888152566190938271687981938384848516336150593727459416441200923052250203654694932418976501288689168562799020465127021971425669087809513122665425105060200743359302335228186746826462017074164973613348968376906152715895981004084198910573785772658350673639279963281550625069406811681179346071535103021852084957812200279279612987462541553235283757320948272474994143543870563418789706203643361436780863874835840622616319838227223396388628052970760946324281655551109034160725569589129531160016041637357700881306037308092906811670429821479755407576346242187409680557428055766030690701358121039774423899516803544573009080712283913359435506304282562728286020834589555188414633947910476418427513587512297873993958457314436373567698590745184593210322137887738431637041317924668478593076691664316421517159971409044571918219437485072580107132223229748513197098717768541501117838413171538673739874115354613616120047011141185912129372860123240615321887436857038645940392078358710462767333302926172008244752824011803780271956658630320473426196240334440286005180364327193277769360694384397814836475190582101186794804439828154808279712004915512372834817577792716110831266944762827556382542315881439343847243297383616334272367521418758187918140654473673622667296287757680169379091950626817056494421819486415251826441022183092695683446137847293460974450803025549916135832379703439455164345732364654604697639444885548967432239270309300836377495790492589652123534386982292509077861036944773888609409229608297450741674109146009496914963938450255930351379237021092770651415452578918455440393376255270868226984536720777971097951521546728351473487667586187894936606626349470499435494739740055588352283508007812212233325399881877627157653889893363728504818118149808183573117141916615828672229143501341643173841882508275371067056280973058045800639719238009554199754438901656483187085256870207662055240273245757402517156627406533598247589710577725038761082257784073498019022437712515067315744781339531305709867310587066929190067121498219535393853710686566715225821530010541063913704391577414185531235727030338092880209291066325876403206101016874171115002495834439711774076033270820131791065574983023650048736783669226785719667919044308040219700564531132762445018331982936200453906852031361486013492787117398078288667671192059365222161551135973344553126030598276700490770813240166171017628053001037455184366940985180165112558957854565944090578065001489082058819257035631562990129149729916311360913624908585608607129265301079857538580378246690821313435610676053794051335575131045875579518564501294949492322157813239892216143839768569694878029235365182889596152882424765868964880825937384657331522287904238361673244342322763592399162174491610314009865529256354332848135982740629206641314586984892574395580201327082628815322851677221833996009673665368908545069799352270256934220028990997151650710918676055881025101816010581997950633006982178854653673370576769024814551405577851006227076971011583419053332936512183387710322341440545756984860355458997388136115106920526193705115352330297352576546186114039886594696248310155170784134318415321359724990686669814376399075801103121434169768469335098516142548110429818781636180318357419420084487831461149285220165788858505996187959718863254911157271723381011006755214068311487165070159623942039437982725952918056847025169231585471330194781741666781348827465867862917350721267174709880170840581366495181681329893617388316852478553561813702296627437158410832710072411222122225274958265919475741449057793247756627686352654091818563246462122402057975189161185487029535469041087955169156122891547958095738518996619083078457609363165997064372236106633334869510018961302064782460295042598878290566725171480176526985518944008636666836992017421264981103934507210037406188534976724431681800310843709139228571689395891207570865902888123898582080978616726032353646185641261114182461006015740706915659232757512573853291835790031470878570747061358450488643287301511539228753443580821595808981683407109064614324920724641454583254128390893547355399410906877351350906412981688655414596366158310957096088004149573528999101573105320449320810497008914232045666117657673833555292838646904903643954478442594144372704856109499851012170590305501535449712021054843315778637718582467713284957915954282466939509435062191126233618942275567683757087996401197266154366589672760319249134472243262281020160436271374877447116977428752036604384049358841444452520129452568253122407849136363713012520283186964643915666766223370191052464030635294103014356579835465123293273786874779703331112228970043910129175915698161196698084918044709824238729024554997659856786596984613679290070884079023482173854877249917025131580587778778484090579500436935156045877100805637456138336544042336221298926235940144766824183956713697217125520389422736930103556063689557642200357521876182972922093280305081400771491459492668931681013453627036957737225611409313828012149015799536585707030892182012930399536772019744661897598199104252255122641966392723378050279999877332774850429561954772819480942475495772707281062753800132644238845168694289698972831912062875143699435738323235105574440865606303931351941696605860294100113416697456440627507395168019841688291014881668508098146744862744753783002948291395738458562040088282297512279724757489276754346606479759300060643629871229879098580801773871365426569689244609906131160887078140443199146345819617064409357253052064783652787322901036416083361740816588396028968240376597309361573206326353626481263302897479086806819134240239468939419340573608260150414319736467710886156711082392569815874605074989417074354712027600477762620554553897120026309491996304979489625914376649182962927830213238846292203418877492697046231547870213381741251695115456207372824576528982952904931918107301369682981211345352295366419457170683894524329318646251685675972084399009556232091419634718895775708168218847086679311846505312439602568901571107169701572399759444539826149714752728443495606496928138680776319663229080331321357252984534423122531747240354454553574551349496356677950199920098333875243638821700535665432490264576340253684103820188891256979311192597419309613224594428739852272518343308750102421758622368496738270978813982054627085082103807282793643724353184320506928232317673978511293502080431899735047372173028061485350800503001727561148298284118663438135362074223251645006862714274000213485855374310241082679815007503801270208907093260165117300639795115877381203625187032155094869135249563659703899825295077330516263498232605933221526576029562358588117540888659154807995350546335207720287352133216746076911746551971735292227139221139845525244300370318614061695602081457865103939447699555569977707633160886602325984940507834904899543191764286019319785457217902851580433166811714213316896255744474826628701411601872589477133411957739253394422093028250806937352771665977631209125841623307293713334296955045413791665648169912284245579863158479684710438079176956252095879162416775555046396618117581043655870459214830016833499208424282523000770992999189717800149140437760784717207919925730404731842334018427818874538733767677981422999098734705539552717804363383767804057471397213890367647298922326998818500837781180168875521012779094260561710967389534156158597055310059451976372494443221453485405934892730399234075695799631930841567825705700616173062993645814300999326960502196644591554411546669949772553749272140828131663952948047084867507046712726498709259890779034528542753799203579464745916154054976341533700464905873676730057594587003405589425752841895147114261575453211166943607904419434343768461791282106561207616855796592548732429560071080327100386625540300747495200836893360988839640782217921989519639913037479623574317180241087854333226651528951522109803832886792355329175844474582552800108801299272939235895453939363114969834095813233906687070631152753087908311141016413680562957081026801786944338407215572257829538799600234545342780247019479246027723583203848821656821887634824993145759323470367425202872332598816139598209143060785730621242938507937129256960702474302874025484701122915235608257874258216811342626961960431506059039862341567822650783187307526445641603482453699004124657189392275664880439914242923302798061171485113368810704474831523572690871781397797992458119813136742278345409117088897129258667201716315350817421684829096495008789028376160153866900165789752827615914948464265863901147045201756203227771469326948622414776971322584608149841633535850586942846017980631781646019530317690173135803858461589290028484391607645408315341312853863425648132297115129319079719164453699282020571992393663754181736597182804250761541342978167357279117929660257465390418467891880983908309601699295503526470252857487912339203757362774900609203202871330435486949495236529112538609737744165269107330840881341029040466552887042398448068771446430631075392865055229943920501940941380325270447711046955191628299273799966781981714003592668265504055948266428957164568580826001897866343504684899398768748467600377628124000979989891066730300773028850498676023595631156272482193956471946294374735164418177597094821630042332586247665934169608840791909318909411496275918339767974564082995735459821506709121234376176766571470048414169090101683466589861093334507478557767259390363207118343919642778839812097238645638989095635292658407226841147609478655173224947972003800578250578489119912946868563224720121824452490112009769237764038018689064844129394064344057317281670620547282130563951914569870022918393278880406167001731103420785541690479290388584580254774795898953336691529228727879023606868955830324014140063117888320842287331929350923103408901597680595386447227724882667454406174006697913110991761239630911629753771001657267932350200513768792640166697227439426628945256446922809662236967842948846134734850868238362209344229654324404522928247815115260775279547823002024747213725760387668473802164116068850560007709415013630800822098274545230780791361040598620360163420822441069992537914793632217387504916128932621899123253209917051134784422791914698334679234581229354639945845164687785442725465501795644683258948897325031517930030076167507522555347941240210131026312399568789356233308923814364139000998351526478493921513515554150449521979670277228645098232751845547499100681758117417822373264130212251446528265330532168718686941623262855263543615398301556485700864963232333313005531260451519508294418677852746412991022452573154570104920153181344083972119939192126475129513996087080588845320148316670729558028180650340052758415677703428112078485879203047500613422212201434286736656616921267012779829919092351593087935229861604499612167162491990307943321638212886364178402865427544568955443622878975362361874348701477505874984040720699740015473225622319459872919531209891119049662709430558291729287395070069999947557141002632375628179281193247060937243153858127345988918129906809560750850748135776756343937539181253095650720621882705000074999215242136055090837191111534183363056695477275311058118811537888724698714116255590705344580197109058474968354359555492768949341016422859571483811459490331012763416519461935242553797620691469877181683676819430123318354739795003769859613375805247910075146409908009650497996317501449996601126890875976368933382345527235439006055996713712346891969322334949100868824955353436961234832404256065563873837029743171128788430490698077939997184823615234266068989587535666252654119691320208446339793788656289427103293047897794899821550002281126526148746205249776004523202207007520285339454660858875068215042875864577415724997772084021174128600510658156484727829332049296321933339702590812927229239515056303845550624385269935180761207144958667435361522227445346447738418655370525599384804679062969148204598418578719530681260477304599936181519661595013228995717088945028703239143935066091214117530620762180150267882925125751417614902894578302169362631518963514779809872615461620071964106225376310983784559340071026747175566283650223755766479817321864294848468229404336277414955310335132512778423167959793589948785447631590741119127752246380912628824601747381091182134563768615840485300321323337158541280912473983930110703755496611152032213460864718710001865781253853816497049220877893899133884433615474056964684919873495313582709655982985619190470342121533792496478842417320761275661770955870475635350821382705949372341696350449011165944892712801783028809220335777873949051968962286244852480409013459973633399109855065882557287900474303157912498684493467935404920612756756567227971119408410823631227340306283084496287495755520751316514609297136984218034016657490306084426254835627066282990534837256566958977561813766386248477677579726012857133845468009943161473286168810966517347378138879060734805132792703282184207460702455545117740811437835945254087188899280717741956111371507689567953470232114577589414977104235804737166588555695643016089645189752894912268945732462042264697284288979386629600391555868330798125753028690167604093844178281806342172462516466268748942802567328415714230600932612254980695214385830524359437734271410592623355714108335098023558292235070570515546260941129337888767449394639356088805631810024512092258074236166126462058342799494302078876101765572247476426517966097981429072589865618692977256779178554222519892552605704346853835915882276677191326610005507600747631945438517600555598652732866768630308400327941701206464655153044856200129922625730300941082396738211650757322204960158525045795362862674240169763178966580071985439529707972595308165530292548494742870624779034172372926206155426949952798793750601300385174434330615722480167056474560187212622632310646607439746994558152710118214567259391460759023416569058496134717301211713771843625500398757011550057834085629853427040086498627495250760948762978815402232638829143409294801398326616823144314690334122559042405149393087384875902199052000770882029269602789956830203068162650689917944021193121662569409107656408135570295318995948484953602777974202229944503288552157478096644233461005484439081850406483417434242368521648525382732530942384325239582412011898979030616958484458159431624709560812766338758585053777872481130268645837356506031551440943286250196280783932267443129208850553815091026752126466443288636547593547531753999441716789547340874962080453811874885461383278040333809653751157676264022856774366230908077169404546676193345958122872229424981260936730139152289103789422524734091250539223074258906803030193497336722368515196256335659158549608886135248110465467487990990937047954953394617243491031757862591597534713948960382058579869706263912437992376195130873557500546245418418692702216536681390882378323216012189046847077494399639640275606967456922769185486723219731573820576536921002882663764050269097701854104016866909985390198009461562858075111297020698627512691607202016766561716618652211847663495089524812150017928662768337541586517243786997109827332615686152781922988063778373185409686361866475634165244267980366831538805088166321279946114606959507414418744719690492646920400030796498671632094839876555042194773440759803386927359912724872982475475912798464245771963212465410237956729948005254807027143073547379649468179905217460416920191752898707766688734231859494027932480822918937958208951966104466735553153536200670199475676463303550577731809140892053890037359307668668288520559423048961278444067023868872784899627259521725575911487394623993329366673463757572878315899686826152475979567074263603192879865563220409846984608879088383299335748462682056911386108752838353106947450622542114129609433304559567570832471675812209491631508148162243281002196038479519706920714894616968273340227169207352671972390859059279017970092506241116504359217926682202402122884966302624154760268572551961904291449869113558923718172371123009707647025741650776995645795050342648068448337957829196793301264807804164654955927424801946025685608344284020765862540514178627592787825131705284003085383809131887338871953772731720712090116567738168813910847994059069624930253335401402049764126324723234815502829626157573717979978251997424677789270031480129661969148673471132444423321871601006398014914687371805440802141150492356502042866052208274771400768100721976735654431667522027943988591139161176638863692854574704170297565003136724134427427184657500593225690299497412540410301961915012494316051296796766602219604026722715933005487543445134523952842150624590619854800410905788719746242433664552030141956187023856486468162537454111464817852194320592811731656401513544902140685778466979417040071569326329636631565384073243962160919321597608257708179985360141530783985576708457697304275676445762570657682951218924623279315258124996192076314588744492954915629792211298102276067066738129840909724134106207896271946517262788430340097220350496071528054216999388267649495256532981227924180831248931916657125691124228347672916297221545307724701669738067216914294135659771201302422455532953116819400354980074428191957148230165576339920925356873237887189946316221464496506992216084933302014841017788552688649443886830122515283150153103384142032046906451227514408425665044884565371082020443109152938932429205903649676360103985598630234523037276614794278658016955429364042001010774611517351999888857495673802627392741278046139792869318526232438455226193233866504773328362496880022716565825651991833950902342123168458834459124980276236094716364457911220564188249648151983152371358350746787983769633911430527857390840287755691699656800558025574674190450639507748370134516674618677258322865243447915819997419021599522990214594396087488663928918880961500686121585053953639822999931306189126853350101413625177714180046586217028314829061448180287861003025546111892632978139629631353974931182054727885760178201019157020464749595490764012344524133287785459580300122541203561035612328394272037934497119044962809865916790180363017613954506406601058638449650376172978811914322357383428188071674803665047033419453993122938796056641026989253567924110768985332950959740721747881889288056127205408018083978735154462322871503574777629234477036055694711121070877458776342035440219586379269609349619083012292043382559398605095939061902389294209331682114822742138170497735024291070020341950459134108656564816558507888334187522059797832258263669776103293681754760515271672248882197117670418240165121036222602356867472888400264495433923534289816002514615102891947429415940903630951884981388200869717023904674531634045835725614611994885850799621980334729999047113406079327024629551627093687094142436861920578427799452413146703705239306861655672398565829208733982774334230428870615442657688149364250317236726922267579525769615570722256995956860082173293846044735601716142997654814490028832650902313833376072136461559952965168301178615365032491952906052644857958969003874415555940400097159732494110116420722005840250966511562715747101807703004949485522305656911254400679244569730690628368771871114002134252399190370143011266859523287647310386499348382617139768245555717181618325428748867727414082886975824490251369870659721462609503104337831810608244614211046435009212626058114886593344676052655422417948298340708984263364205035407504487872716248025957831878103474349573328907272078868111144796395152694676400140794081364295138686363926810523843641806564707716842128281479316160826780938667557699025961598097195209821497761821946922213305942100643000540000289331370252454084706739752
4589148395768960390814424693211327571057131254804092397878602494359162625172646461321532095288268365776047046276727128568835736271059811341306298507077736847614032703924675342367046304585676350748500846291455197092505750281917669897899428728312428278588533703211941746258455108505997053221037593778663318048455812675824071443762979715624718868627200735832440916210704385599618571978366820680894805962125206416399689156684992495496732714718883975386702128756429073206843272388057563928122518495236860462779159521629605916334678207120435746860251569998206052845319754219029582017336160627005528217173886515338464602217823014573151679903228509087180870471906863580312719835878844558980704318356195554051469319791348133589633529578799449317670959489365101795401476337290183202223655484046448114392016017707551891188297309703278968464580663095325096735816396503138913146463479698891606319804982558768971182868517045855288978353256857186848333439577785224027967517469966831411041528259801938625656320433743777478448179625650204224277886450016665313236246928133151897816464647013329170368778747863688414188438317499512112692429368175898899623858257966090804683988920749406005392254785742456655305105787299988564214654591980777589022378905866700512480117710022053708019120374984863095285617363479873275922170328481327172409451159206174992648530883401862331161070081461291545523795157779872007945466809144414049075808091795304517921832441059087487800812755427872474605863389481987973214976186048548955639508184547513287709138938713866006375290377782606452716817757736982570662911475936139452511190068451104526682367933194653164099868263233043343078019888959386322851135483259284549257241456229049457169022432512609591120037981978253806466327126335378502390931411226400801342030000374159149795757804880798964112257758326728131848911916214889109152984637278909786907952748886571952379481863784118241616312476159364204886351488083123232347068858719772286069041156369962810890993808960827622426589633038107457908756780677207677161719409839645449984822084962608640349857169372526261371592251438642337178748574253980837712320473969898923947226612913435716499758437911005219827720968090922524435885141132331809743622834125622032476341132344509543940920375911065124167839983839804778998344653496496271255855142979589170648183380368062624614798991706304723805776099931428206906126513469966021471218331960991740273003484489432947367567787731210781424902866318593575352723991168492036284046722809214318701581037760881695517971822748904652840727505348207996774331770883055054744412956857168361098861525307493572165663403923610568097097843901116167167334519305880345078142407703948791354458623011982443034094086061222536812834093853033810778550218486278213810604761360095625056695122469557430922758002924283703422403981254040686743914419274523148955499581098468428647188491799428596543143307432299240823179360379763454788521232592180045081728028366029558346906420066354325598463146749619731054233695784849878759732170635629592661546348349127079756817521917837650072537938844475771607792170043113291058505445401455108193024646917292724644599646337388566917627796392815621334980679261573025239133103728382267836026865771375864838150828968213393034831964197191655793897639511187828790052969661263503893577680609500093572736288982781728354318023241471813708830040483961876209478757032958582613727190404063669348201879391434177522041331238514329329452254924404740880307567560896786209301282687179514863077109482581472973141660394751329117315679884363556043179186742919311216698964686539677838701153636276041429956492241577969242993512111392978911030264466493573166334871182526855348012286026013762073769681631375139414038694793334080784040189052775341700290303486536904249727859737449732613738128131743908820000439092052540178798176204310033907935322992725963288128247145922872252627631346438750804124015692935401334317175233005685229616829828146412255296565253877276970585327553446697597627269168211170089688241992872738438444016209557231373117552052882336409224617222087543269915474645806450404505745212491207855517755125505798038369714389308217952261670167771839392345599214694265262903047292766840508078527237120145464795401924382114145856060502323484748264540682416697030163419347219817387137651206094015015467504093296892893318164698495055107657353983360981842492643980310879051532422015116542353034763340151442503722619108437870881801313777985993587848088561985268460326323589098021051081441750542336929526906183969047559705608282225361007937672091552590600933677133153275535892280232442592882525510529097382133759681968714315754577795694832495396836528198792170619345476481389581048936738142750492445940770291195518826864156261190683187371524803121821580327138670860901490981650278796373588713089376257800087690197480116031263956510067017518563304682413466079164260859822320828345876512565046107845658962918674451954168079810754570311143448676290693362079665142506562801498375165543987139705304323280539940530307433115565277077871412674172660511597873778230319356987594611384416719970296893834675466449443999320800051214436131881695651625300856313615502312817614019175439921902585325711310444762008605792545967809128713549226686842425201888733570760158862096952853958843908043158530836791515860904720168750154550859959277753261895152023828202779771316701944479400395322850106892209120928460130731667373093458378435528701536130208247030530480713954841661062096746558948236708431244680046577698468080961101094718990793765425750106391079378740233238759503619178261711399124756520638757313583156564150672917113632418475669282162494898208774146918057194870473589941445023320434497718433303398136526919512887323423444375870603500780117571094017370271399230862039360104225173718915140773123468294793532059650459305518472666027315681187735407672133721083685426498112956371092282325459230700546306199314572129316377666274709376584129816445999986263989317073152156460035136260641051646442492395621973270984209323958297810588952510935318947308561146388095100250066068454407080935563317151063986849011272104405117634332080492879724438062605441022741469534132085307633651242898024384583896058680730011108821588930096842693312570115141331583406614406761518388621465478749097786387990525516763215281226931450314722194399445633114244856084044780007728936398183981040440854608035383247068187908309662087091235147347277247716131018515350641039627399617201294903736892907616811820294718856311420359770038849306019195294422092893267291818238944425928576977699892571894338085199888533229715611491017102912968874297921267179187453536992652975850013092218719096994418909194509029857144444027928564279165402096844212110135143015455199940537064659230636422337843604833302530563053674400220894346438217297837004275799939512935954599442437432253359034584303538692137641127460672216813268605439773004737419385571156123470343861310227010314209884297767288617236004841518493018227439259885916517443297903307435323049032129362385322655705994854823725173844834292404175871791830508312330998362230094918308851419438946127502640919703985095954348157457122953140702538690069944780198296673682586057758134036451024530589619525345209176169956429643875982480230822731382118378231453152385355552863651211529694755368824601503267454007247654160833775630841951331442071539277300488387955254912574188939523169616183769969895244243172556195615925926724797428582230108545058660166976962972495842118911583151640159861870384432353708412276873187031114724511483264484526270272002294422784882145023972956037705269667013858407236981762137429162980486153168315806756988620720408830995157643500383926745822608185334057803325936828446233673633254390086774078870420611279810578093137702961236381613392901158143988006974175557134457034412568349469379565001413618864115612173096482124281836764972397196910542631080521731201166786885542064475163434789873344213266000108099721376788183013834011387171963402362684230829732058072968828678050108134572568408430206453507552788439850353935309256715280361280403605958008513268682992881243199745988963919610658275473043594637740552148775454973401684660354127343039039734634382260914778333155060181361792647110507070518936895933995293978558574794351870541309924855738786167939859229702509085235756321312796785614597818818368153511045972714832359023188556393304871094697001082255788419810508048067439528841959314544910428516169238198190636068231259882932245581123271305065546666415407725696799738297329162362744751809427911408668805738122454724858648887097874750109455800605597907843842374886581202340782535445864596615886400256109826227242354963693480419982900070468348859553304709512068184354719416634850794085371422584552358584132238453226656769085971499795442706990297719563820844511607994979369722639232525149214881909251380413808432117170339001669830729355224293745697375736019266234575147026292385453706245794961264296409620225267490910216940762949040999355484129506930754655016215759159869212846601661397917207794325915561723798684253523404823175431693518424146776339764126249183947888095139975021348241330157949022903535928415145435852852162485192587977473504925031593293474395406578651431825921459644515403387463722734200824553376711350581542653976526993039573652369518453170994827483454200811658620169277229695090418612112518383007419234545068654698173166882826651451597340694535911948029462613040200128642904344391178018284496741166034059148114117009527042898367077659342300806686760104077276364366080477584756706335492003697082488369756734289197786598311978474490266754079505360813839143944246280489493160040184800614734517302532775136739723806086069702596653506375445103087283559460605510124081580872159109572182738727111488209735390882259887545924084319584458814323964694142029390237783927307200406497346089893442305476301911849879293576483866491099589011327408673275567760432549095268982266888424857994734719112953214053218299207036371628058949902735305695450116307560009010359268695494440332649731738666135415402564523590685967732470857389900475640601922014383532199529224356307449144697724807872728216929372569666799935295520704597434432560065993144773909734639323735595367962234903819982233770854183590251487467722763534548072755454377409107494141715317824231929397141909192633897052228141402599429775658433356583999597535821404673395232489390029065964243813598567765965767430134385715711440512130938268652377556121446765784706945014770349843794787470246313936573723329294370979156681508944356061630414094282235416075960196281116226621564125913100929913483595634006461825388564309710021999525558929924019446777749854342059943790834767657726267620900316764155262734656620051646801730740286689509153692074348770653170931941393372991877238155668237392783020321003085287267688290932772061264558876121545011559982251545445375866080390408989951736847442163591749408790773397076213934749367668164670081849788445073039068539508182606503133259918277968145918270082457483532412151302092324966642200394403701728662979259851794448909078404076501671572297398112370527659753635144731025336316945522708144218108535799859491087301489528246341668449920957684032692857207424152491383211144172104383733563985863943877727261102259979728257028034277023096289804503287261688211783246826017597559328562379348500499341811880191323777694079250040651487434174823666722159710127652489622019358073073726156867796339233659338966401092343341114389537612776521807083528719746477862981292096063360513451296916620287854289476679975233129349726568280443334547536069371922101231837890247275526070776582004347249832559982006404309554134917722112242141148536733697261693628717223561626130426615949889793167547556221119467520607884551668065099260787574535069559524605951110042658634358776042458961494520541222742939287062067025327425378939727347831897040730548525760271472669906927769792872127290630970475623911417181697287180576216510504722116054395049552840529958097259392257732999334382848832702217466961663618451646453426271613598834725126310535342581043801344025255860445366386217181317474346894552423743858929230205993945004666243515123941311773699801743858029353302838324832751746441605168357902406415583717266133238079181724482161009517153870604777419877795712963671951153287178417632204978795113951198823430640509243897778227992039616498218507949757415808504752146533876349700085146707730296969373995689699338648473118366671592428650562558172330173275214705157345128815233904103043301076851201523751447182501326038330949306422163423528836279124807895501408075220938491788552502102356384231377361810507998640823489266490146583332480426052144191456164048472202687397218166476579899003359703261563685893472072766751334986841332688252515872309066918592677932642407835723421505914671999105109543201253987584266186151286125040092330458596880413286905086853411860138226136586252336325030515153471622407707567622855349930298706097370144114489998672032635166361908785394443837739883155570253302381392055583657388600193313884963759039825486847500656678521608172963989273502261891615645818476749766987298328384710420348446189364966025072599485119285359126019167025542670927781527619301282314769850903890894549163547184106061425902861715421214885985743051651164843881614476108179469196971550401675331099239312079405081805316021892900630797030675125164109880196762215684267278008212293281505257642232596248991154483838993015902729275602925524602247455961391233030088151350659761733362497170942793014185556527926968526416508510889034056819704455859497396956847321590461781701886629304514432889436757896425399326379233328054418119584319624307368011065021609368606684183488931628274736257324934868371583268764451327108924348086881894310841253214115939223636906490431550891415315535540100620693370029395153981386700165365748010101044591852865713995304877067844696264329757196112361231012282417904064581804100683348449411143647897486534951122466074943385250465939408020159018593991247354251686451255325112505014149201109004487587073562600398164421530696961402719823534581125883357322010661791522108269977899510758887433913341851129608333553838079524588560880250837715653314810348101691912631433781906903562783012554423670538643676743332378930526505835364385769476328886743203313965434673760825137367887126762723032861963858045951909941411533579183953805900298124475230145523737944298061088152271528714390481913433727250622743014751961818243527084220982042497830171262882161254028018065017909378637127438878566629586751566789875717796447250862007146557769865994679888100389834518844299868346856899644617167291181581568217037478843080244690815801084957725890592602446422845570782286576022748416292957954706656181487155321133243362255177699742676266146822015165244516469882425152313126740649338259899370972338907445778178278875086054577125670769929362216340897853646876741006556199104240623143615436784419982130563438599692643797563419378440480736753358421884648022640373737638180482364511934535151823875889009599850039491661448917482764238170409674154411740850124675231777534618068518204674731966209315478913179759213796786147855504560882827055988656919618670421467609724919178023003753391590093423329939944963047703538699064658376866775373557874497107980803509757110204434250007892573167180997452348604862191988548049270681420564401139751528070597328723257989750651233153543379221216205417897455416671431038348418378881536930188583677835805813293510489236690823103923878055708251149955496971704088905861384655048304621834151640207108748311684837994153521143188451752232617432648389307262482343241503354362960165312539421284774454837302322079679920061178649446009811226886523060637578237741418153282125693885062329585361590870759626429485743671773763330205270315422025286085372950657414757221039444235985076879857694148433009328620386497617093622818136478544322412881258504403275910172675111998597928494714893425638648521553070892914352093081325609245160291425578893570830615501986537105846036302607632464190609138869820571492281396033006219342277528229119648793378043049126389817512404455857854595608298063806061829070177476764977911090288653758509201095556035349267838527561505500999617437094097219536647242250588555979527740122193238856320583512390346129463905967857067079346807812981275125625379811520675641335290074463762174799862244565044714713808557122018691609650615229026742550726674253624502916913861657922999128403109166589369458870110767650507554435302585848740989545134826656990373369318559586463255068126325225864974004623556670071920055044758758707138691340056189441471799452534485773584794062527645090543834883616311884329065770911594219616795510280554717964765953377244990020072146836881493302875071836351717402955111297922461379400501540049794783092079172077836457525051864934218608401799199515396121559228890419235807592430875203643431086092131710269389203494338830732816023534129849527603512538555555021955326125893959518094944724758971291467000524733977144639121461081534729537430225596219702631125892617592338767352659644139975057515670798155975146079414098974556703820333922305125037060680177719644194735337397518482112315427894411364131142265607406245229219299028899153955361811873812495265680547924400093678680960467340698528652258228490612384652824919291495617194109830663867479588617458073390927731336337788081782300903651671611167381275870134278604533509730922892933369525128144346440398909202670699142592307019208592729756315486713562131499099003916312511505249558420454096227962631938971746179077296789888551636102300564767884278014544648243605197118482512222985312912100955416375300573345323048003630860423729821889911728231175476104775249862456264351219943752080477291861295800939206293562554374070800405012550601091834513074197027306469324930050868918470709695791533642499496750869439631257158486144817440857486983236620717609044363497853577813104048971452628139431195332499040504086781801680981758174241503441205884223497145603634764593482946418273718133560086801011303209565518509635408099737353737965272513973286707589520532654655022673810963833408782670906581287425894398381093493628203004952811846594977186675416624273418005895098578894224782962450298012811954856522098193997062623547233417113010509591157889723582801770272595111589723770206579658930492421732659831813933194731371285308302659424012853597124643415454767753318854811415697700424441850381607016779897689677765712832812984913310013761769529825024713406965158028397094662557020992680918799041321559318616494411938493299830016073052281678850614824053736688282560040111478397494093547221752624075760777780662779318859952734017018644790937849401825929454177583342690746545899124797359039039819851747265072548632024722282245539595660941526648556737120621626349909059370141665038336407967571003660855361061146103189354009960171097958037950256987517309059931003942537663625030649405979989349423001407906741734823092823488356511593700578186005748988584494761054377869851190443480701289566664201347122708341834809035638344253056078383846103651103116635884875665615467462538959705506318377544307840797942843865256356260039027237393427661140073331947581724598047306219334890989746233542575015733551630989402599704568412688578908648361382133552307973086906849637659866544336086805208103976650209577488690970319178841664535916270995054976696366606620639049051930037525158487657062721966683477620345216365786197589338781194329739356902301532543756975061444975196214309229631355927939379082644902263816823001134734320124532597734472713925656745982626832560208211446177868544685343692603793305329499510008759720006280446982712543919793566457346913296545334948843696658840693245381443031211403220939339420349823942092120576275676048706871450569159221362130526384255002065132803699312729519507746817807623081272815731233219314842203999985780103261298054260720969945767517814999512163099380869269261252502400410303100572970940559871833312112909339180803486331625714774915124689210639087287884552469355657256302970302048480991893008273454302040793595086572301953207792938689176061503381053743554122933341987965048279255212938336179071518902878894727340507489780273673207842201173808422400961754399338630116734453384495531226807555077743114455611246852920493949832858915275581020001121787597602340803608347237278466290270437690408037122373120822203937496700880983313840530519937896434587432030654140263990214368632455603899205032932405932052198330964491194836367802840115835010456151935037848172256936294414499793196525381129472027918920239329623821827400129640556911916702718936215618545969524775358622440377185101000266020423840614014093273198922756586169158910449213181281862498557735200757621292078996100761673642698828613149247532051441910714660485659383143393005345405655988055151806894453898429326842910574447880139653377666573390122684937443322564789654258330590093711484193814163367413246657301087553904921047639069653764513191139346916774250312545735921393598342084687154223843305173249453591642326874692165477463243

이 값은 Long으로도 구하지 못하는 값이기에, BigInteger를 이용하여 피보나치 수열을 계산한다

코드

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		BigInteger [] arr = new BigInteger [10005];
		arr[0]=BigInteger.ZERO;
		arr[1]=BigInteger.ONE;
		for(int i=2;i<=n;i++) {
			arr[i]=arr[i-1].add(arr[i-2]);
		}
		System.out.println(arr[n]);
	}
}