5 300 2 0 1 2 3 10 50 100 35155 10987 18503 47176 37590 11702 18741 2261 33482 49906 8844 7796 4771 42888 49153 4666 40540 984 2431 13458 1919 13090 19288 22711 35170 6410 40442 31048 40909 48706 26278 28331 25758 12998 29580 5834 37944 17919 10969 37987 1589 45080 3925 37052 38324 40983 37159 32164 7426 47116 40998 11886 10546 26763 16926 27341 5195 12238 30743 28978 4117 49886 6328 9948 48712 22171 45179 6975 42096 36234 9641 13877 18075 898 42518 14936 7772 23570 2294 23918 1925 32087 45888 46561 2870 35473 41914 33542 4994 47417 10482 48499 27521 15064 40303 20970 8897 44795 12696 12375 5767 26125 46489 23387 42727 48942 18521 40259 47478 3606 33576 29523 11992 27007 34425 25819 35621 5048 37769 42153 19085 31003 6976 24806 42391 3953 793 13398 16244 43762 31705 2322 32906 27880 27693 29945 37201 14570 279 37003 24846 43408 32328 32866 3640 30009 5533 30702 29537 32505 10915 25805 25435 37274 12877 31582 30872 25309 10511 15399 40915 46094 24202 48690 23183 41869 30082 25347 44990 244 34739 10439 22428 21420 43824 42720 41818 45676 36358 19050 35821 11388 32199 22799 29324 37428 41462 9462 985 41330 8766 5965 28883 45379 39066 25983 49136 29078 25639 5598 26913 4637 6164 31297 3523 35891 2569 5375 23980 2629 34490 32887 43118 8909 10042 48668 2051 37992 4600 35246 43636 30227 13451 20817 28534 14960 5229 29152 13732 3964 13734 24917 19023 21792 12784 42115 13542 21995 36362 642 16548 8504 49980 33401 24704 32128 24890 9155 25041 19954 13744 49661 2551 27678 4809 45532 6071 41306 15300 25573 36077 45977 6997 5387 12881 271 44313 15508 20742 32181 45252 7836 36217 25219 22930 25431 28775 38600 10875 24167 24115 15528 42940 1746 15479 19603 44367 25903 19966 4902 49127 5753 38261 300 3 0 1 2 3 10 50 100 5895 45058 45274 2624 5880 12988 10481 43363 15648 35965 19519 30662 1873 42160 5680 49881 40702 40454 24486 10991 30998 32270 27731 18399 48092 599 2559 11348 23522 3297 5112 27140 39310 31145 2142 23400 41922 7427 3396 14642 45129 32213 10740 36534 11238 15775 38023 22478 42901 15848 36495 19353 9959 45148 37777 10852 9554 15612 1303 9184 33755 14823 28649 35026 26774 29866 48962 34912 44469 14702 29371 1755 15068 3732 25520 13992 8310 6366 25374 9710 28433 42565 38223 35762 4742 32501 15917 11109 47208 34476 24818 18513 17775 40868 1660 41327 17625 44327 18793 7627 17167 19907 45171 8120 21009 33790 34312 33699 12932 8818 36403 5030 885 8008 34152 48680 21843 6960 4180 43593 46648 46729 8930 22006 47912 25678 28945 12009 28425 16302 44 18022 3187 35051 30494 36991 15324 817 31589 49240 45874 28879 37899 16484 348 20429 15269 41464 21761 34256 2674 28431 9076 33166 35984 37804 25987 45833 23596 6280 49901 46975 33255 34458 30979 12089 30863 13880 3667 42719 4432 12872 27837 39062 20132 43326 40121 9553 39046 5551 1337 6595 20862 22526 2588 6005 27178 15433 18942 36559 29265 19365 34292 35086 4866 41629 31353 46665 28849 41750 1170 791 44236 23888 27174 37 15401 2756 12936 31130 43007 17106 45644 49084 30869 37378 40894 8417 49263 16200 6289 20809 40319 30540 6541 36987 19917 23341 17742 13144 33407 28685 18274 34507 11214 39879 32506 20844 47307 15026 40921 41089 48751 22866 37387 7477 24167 20606 23978 30434 235 10690 21432 5691 30745 11459 934 26312 37845 39435 2923 10807 36310 11087 5903 35478 29417 32048 43348 8930 17582 13741 31808 4698 22787 6270 32146 36096 10179 44106 32864 41280 31235 2835 30093 22165 5204 9060 34983 39436 32998 47080 3069 300 97 0 1 2 3 5 8 13 21 34 55 89 144 233 1000 1000000 1000000000000000000 999999999999999999 999999999999999998 999999999999999937 559134226826282225 10310501897572775 811832062034693268 92570196347466764 433528635676794424 192160837663079361 895673621062212854 435125969437587407 251508140640038629 967171309857165550 953951083455374657 918554664667618796 26959705420421439 465725114465264080 126312034739666592 776031832011828330 39579240540137158 520152993370607591 948155642263557337 168247174643470984 101662681156071267 830654336366602255 38370351115551660 717842139346737277 392804169875506844 983104689081845229 656377838502994659 733850981082402949 767175771841811690 290146942776438654 596320989328365592 378806566675324040 487442512363166127 612644401259041436 195112562142338610 62699896969284241 294503593670420500 98040809982120631 272715816423519089 500305689756000538 89361864866922653 78622400186750693 793564061716899549 732664248676682164 697719318859388877 216592374368526346 644233449545688615 385753886018005316 471579450752970537 723070065324311653 11941049165351561 420351279300195074 672869438772982077 645814137912801910 713893605908978489 495854823082288409 897745280609723110 516346763263040595 872414643684091643 967734850485997241 945530925446854753 984781601396700361 571301546928507210 397291060971973183 888867353616308672 27082614843076942 397287835985253555 217347295521532037 50889748939938748 519828942659216258 728443564331416823 454330382169383096 776089756742507308 770062110394848781 397681751629727265 448245624960493452 335436455650742677 887022104145891408 428968298151968846 219892205472518177 496411030495729740 986084296946799555 418395522120965629 581090898886553818 90165260272485164 392780740141889922 740035083066615306 70500370582821819 833690757522417520 288659571043503906 783085382235786261 21202605056291213 89299475263300165 907995742240677575 340449521624164798 922072317188853004 455823584538554642 807376608173661330 932154350822923696 238538212935011803 500015018891755295 813249475434915663 180144960525474905 560454790881129749 402693563086298192 70776199477608048 639073067538902553 817337747817903833 609545535860399929 96822711409039373 769588862095653193 117424133097213284 243297044075222049 250846376756324064 243311377061468150 197609871847199653 321180707960133150 574242911283505250 250154916060850781 848450160750622239 289581666932799095 289150858081541091 825882186268409052 309999185354623441 361290938817639399 383075531545026596 79721308681607229 160030740668603942 216200967092170213 590033448280218607 831201414357956784 727607091151173323 61151325363466485 226651155465506253 748673408654594643 92856637086863827 857788027940371142 970203036037337534 169541570364725186 266584987895647967 539494859296444461 724101690188199762 856001057319774495 215875366023049399 35741287353653904 997159099283664891 77704142261129422 261183659392122610 250942074314962361 352243251463444286 234472601852746462 712959059643865796 19432202265442638 995258044997238547 878124495166034110 778567770714150389 517545560816981820 23043424286062588 257802251666977332 822202547056137351 739078098714623477 897475750668134815 768695852614978710 692876784536838659 499195911145047776 480419392969019932 85955405146311447 269379828829029811 532462484180880821 391507994314941248 310697080001107821 79924054451957730 788200615091259845 529386488945822934 9991466891371537 915790725588584839 276326449559254248 39529186674489068 520040534892709768 322293215365250676 449255252281455271 593164595005779793 243489245844686452 985382701134810549 143624755522569796 796259986885652708 660721228102111783 841375286980310130 619210713230152070 944385896861900180 654589158995551350 561154061721253400 66560867686504544 564464518138827556 789585674285058378 738580703308276396 550274707978229519 644017954746769228 265516000913456384 336905262180879020 761802693560375485 634930093725198094 29948975343217139 479423945094685152 289549330080380490 998641298621752595 230865119266912968 458804001535429663 163664949287109098 743790596737086986 876698676039197628 831943946955740008 118883620864738821 654994880353044771 858670696779454987 327254791251770600 281106096600453529 367013836658286246 960563607937659589 741274769520613468 613169203167079306 731371637635657300 915187335263604211 964372019619333002 664409795300133427 643014535188657311 9801132643973453 180050279327536741 772107174844932525 672185625630456758 407281411434892243 786023136832627357 278595884608832526 452903075977211890 654212184333778601 632979928986131280 185075877107439168 439870707249867151 574641317606142511 703404269493720276 584765338769777006 656922787872688726 943895375370796592 974247941619144330 214172028123332203 989215187102629224 948935266817960221 979430449567089393 461420987428826958 422981468103671162 565826108891493770 622442334002141493 11217781329121245 211534443456150838 526085982826274838 6774976157336613 418101243619317142 237330259779737180 549906092846842557 264515331531614412 324737946784842812 150433798052782043 881472004325869165 684056566855267065 178844510035019686 695552914701664823 77274695107612314 593185944382610487 102920691707254734 754004282426729271 919571278107250077 83221154127738887 287921808460982432 352021682499012512 981805643929599627 489290961306099110 835074514944661181 934223711562574010 482550009567128762 568800709425644136 315945534863774684 300 65536 0 1 2 3 5 8 13 21 34 55 89 144 233 1000 1000000 1000000000000000000 999999999999999999 999999999999999998 999999999999999937 184872356394401209 27419629157791288 574093353007093819 269695352054925492 780463120848535003 701122257381456798 782510410511435947 924358937675139218 758717378448689410 709339522882266382 275390255430112514 192506656200509273 248381754728381925 98534341233915039 828451211624258333 646457065452922955 506780508765401579 108198215387675456 513905405030030282 683020142599317608 384130509619069522 902782045560850780 540737160101601080 772481210484609673 160804369764726374 972022186130937606 286851722076678587 505335459604886097 571796817938306161 972492739611056166 10676724324774939 92572800826840934 814966181323199019 905771237420650529 390921063478348944 93731874922992513 307777122551372118 945322625163461780 883032438178631151 191936835309404415 853959150434189186 454574761652183443 605003161537863195 40188718954728716 625792237443117463 589136367048276535 431988764050842936 98902375219969249 21066617438226022 264888206324822363 664175705983416737 619755864474870314 141347928219775859 794221663272491469 971788772645365890 84414578755228947 459661565508008032 20291831253254016 505836080929062560 456644939852060815 189894478355071541 177497616303879566 280244537641353000 580824381172787626 380553178293531001 420721702337826023 76858653497224553 264581502890619682 787587903252672742 866411027489452187 7817008896726629 643133948793306005 499202049919012015 674223830199306823 336484581666730032 392296511872892986 511902467831779329 33244341525898834 534502852465238426 335066154983551654 108947279287294542 804454699041446169 318462789345472812 351259309832336994 415943910846798942 324807804431094525 860373706641652447 246743859929125029 443451283170283307 683509822404820723 71451058144243641 506413039065640477 749819121274111186 397612303937120937 548187185133870094 741747654482437221 681337136867309737 429780978097633195 82594419302489581 939753620415732381 776473376762483591 28756570891057306 269342846854827965 353603679786124212 569674473849437056 889038065325860856 539234153224248585 322054697986898530 413969392352879256 683605657060174048 745899439130368869 736809056935509888 154654332382242660 567561809608902325 199712938887038941 280548864617565683 254981850854832029 285151193103007061 951568190600465265 477125910805943924 342057581683003237 84919794542892813 287509882630005627 882047126177339275 654410697646265588 301804698631743051 192913407899081592 67071752460315938 195955497120647565 254345206170248652 826591629177762707 956873885063420566 840168186163558899 958454118595362905 630265270725561516 962930595489161481 293487053148483802 361595049391783676 963853624037611407 917364650434490369 609527576378299248 998999043885009828 510134606988442677 906759077014749870 951603435383895865 536891791219543744 416691034845783615 145840588075832499 362740004918884121 662643701341811159 995811920514891693 837728908027613931 582399405398134450 708082349599955421 254081336168981423 380312235291407927 549746708176952082 325753934532522718 580406865960902972 759311200545814676 161581038814553726 133894708767755027 836978648700137301 631416306144400803 475306416671686144 950016764806697266 541121967227594482 227043058054582132 348317267386345223 462708838500503206 183910308467730881 148484001649599121 40566660835521250 289676309624693467 360464067970549562 129194973628415001 802981314017481996 402390381964287527 644192775743349094 476030948707439036 780250341336073275 228848593215889781 672200732015435054 297703471660197886 225383644885364884 14798918798424743 133494317392530111 904633983220896076 402457316320808365 208394241673249199 106005607707940201 161332947993017017 721134182262718663 825981298440407345 308989884970649132 921802052431398565 957420504206691212 97670504541954198 475664790630111623 820858727252505001 580176515969007253 965661426222853960 449874061824110930 92852338297027847 643658216267522467 89191542296778420 378310922784532278 969387972442253234 972154398798546911 233204571143091597 86899319432014831 212466152121152991 940277366714860206 218186909485663027 154189440824843427 873393711430691659 298361436603839170 228177049476331665 306368552035308561 557216236590015997 629367071486756139 588757106492861402 858625142361407651 206912488426806248 283170795774520394 558038396631867390 184836814002446740 88668937047253951 840933932971618815 302582735615235722 294932464787595731 681737382261344304 927630432929229096 332096326884907731 135329575440904426 120448284478438424 167246291664872324 592723617763308669 289056590461173267 452628467718013398 689988083687255456 848795050939877300 767229325436625165 378342191470646816 702427520704969225 38060796582019962 839442474366801020 667285427909527648 568565406543961364 223985258002230673 289393604162438606 273342096842432054 295863927104810958 543254945673343844 493662070002733704 846108785594660330 232364042213596959 683944841914682629 873544526593304057 772580154798435556 148287266982924529 583852904322696697 851607712309773488 12458841027033576 241166069839459079 507830393333451391 169768098427938013 397269201551185062 996445302131105174 801339703186099924 604439658126556763 989632095074259425 914190070980172557 71814844328247290 923835511314518596 425625436688497026 774432481565776188 121276191047591856 130553778286801392 106288025068704733 888149619366402650 300 1000000007 0 1 2 3 5 8 13 21 34 55 89 144 233 1000 1000000 1000000000000000000 999999999999999999 999999999999999998 999999999999999937 499499342204581290 24112896123500981 923540472352002523 81370695379866493 800516610664770167 574600628045753546 928800609635887889 19899821895479628 616067417740053346 822385548131284653 730057876978983800 243810948696459849 951324071522737223 312149608500584804 547443233049932432 283363062177081674 458486069527368649 907075396523520441 793271850405091919 107385631776329382 5823923197381212 98530014701954847 656413077556102397 201226679470146181 999799081480382571 753976680426458657 644291279713874822 328618583740883770 213495432723345721 398771296807171402 579286329965413162 24342205292196554 51994737127252104 82480298296475912 493106500762540076 873286246134151919 934608912074803643 556763921589840212 280566805269082031 267907637843453309 177374241160516369 789680848417896809 787021664454376447 844718784524332089 498009160521693785 310481838016881367 166698680474137032 487215070266625874 429389232555577675 791504030517882763 47703145678697808 184411985502586280 141290827405745466 317040593446418508 208543915048640913 702739123744304542 563660607235119851 109986740453791109 133463236771310801 807198735399141512 538168524339640766 586012040100765310 759146090699277403 362362525038397450 674097465988280813 825861819495938608 88108877273250970 739012073331290835 827305880550541604 872279307939154520 86045586948910616 326874768464454534 911079589783841732 240087904168523796 147923760158385525 640417066665310601 246024655589047974 282748675884119156 591699723744110110 305801254392943 64597849337081460 5355238967600448 687867039831765348 689654893504427986 526939008091885677 305947317290513555 292816384347333759 226066284185492515 557266483555495872 335901455117895216 406526039570986235 254725609783492818 103904893491594130 367649221046442168 635115828641337751 891528272432085790 354413010646762909 676558027581807675 234336600007810170 850941234689238973 668208729835045106 360641519129590905 871466058631893055 192939904450030368 694089137113706576 897743672385713319 836316211903246531 177565026582715214 222310970471199324 502956913297001208 801853000029246639 644008868431983993 230213164946962904 568895282647066274 41761744089465214 606927311593089453 235652910229741024 824885841546933726 589868606710967810 189736957452227499 12760565463535329 523713769059971050 485701386784678039 163679003759182466 769192247801425577 269138883869730373 349958414428136230 538990447045279759 279300988684328306 139366405003871791 144517672707469045 691766856984885962 750215328444066410 565321874254360182 624678127891843982 297083295702728031 9972075951843413 509578835155582337 550243463208842660 533768893262733454 774887991755653459 67948781754186919 74045831226263739 464922065358024179 270570555683521687 519171216761572129 232640803825244827 469094997989528345 971768293251770387 668463244462342003 547404786783228031 415708860923106077 320531138014485267 135593114153698215 558041063595573909 96060485894435821 540801673504007549 648902136771983061 943034809249912602 718107616863458261 241623342111694982 780649680963037653 902376325303552077 754748248111332674 513130806522960917 298655721721446914 158809862643009055 937828242093792181 701422872070187246 625866290212082949 282584708888921085 239480906606824455 199701343727206400 922134732957976834 685311783864465681 764401043285580592 347316082486423927 407947572052516510 317218533508940663 568293452160579649 974705073787631865 528181324827320489 170038709026438874 834947075833431173 448152816185763542 881283513288573783 23378947014835630 110793176628982529 390656511065285183 426892872879200621 406579205584939982 659983130091385453 121983724058859006 728722133074077178 603925789721989518 614098991606058842 155632739118677466 10157397055315624 736322506238742836 369610370038360510 924518199825095409 296411595036014647 594834012794398331 566973474817116797 572531016548640586 694564983759725652 733671428388273730 658709156308440531 95605008385425677 287441235959748881 96184128680009693 231348195865734639 169083715185732874 579381023644123151 977734737655771858 131802806060991692 696624241007814743 346854015761208302 291317348320601410 656263693126571352 905941875739151921 863824627673910736 143573347841753375 819697003702379946 434350478423541593 732732141858856949 702461256624412755 237710390061901444 264354253947161774 436630102488088238 332677124283828876 561336210977356942 308794009621973498 147024783438264838 267169721896317916 899436447993181798 238688609738763274 7227550373810568 614600726998595081 631442879251002579 275953495573840874 470100511987670408 110941392033219266 858042812579490323 125393818343302130 778821119527652492 209921835893546229 655523009025863554 550739353062605007 290342958928406107 572820237878803518 304835487339627323 266845100476764390 311608332987395267 893144550766700304 270531984057284604 60796572296022426 148378568928409195 268715573780840649 586571025135887195 750005335987484451 299447107538959502 278184018691048266 511927275540017760 289544995453991507 958534558705140781 325327611781304018 426817221881375891 646126860086886337 925791492741395725 328545836958301613 558883553649388883 834852577614862417 555073775671051730 948268073358063462 576090243048357402 945600945846900715 430738713623418836 291406371597944409 373958980196266715 287933924208426336