1 0 2 0 3 1 4 2 5 5 6 7 7 13 8 18 9 27 10 38 11 54 12 71 13 99 14 131 15 172 16 226 17 295 18 379 19 488 20 621 21 788 22 998 23 1253 24 1567 25 1955 26 2432 27 3006 28 3712 29 4563 30 5596 31 6840 32 8343 33 10139 34 12306 35 14879 36 17968 37 21635 38 26011 39 31181 40 37330 41 44581 42 53166 43 63259 44 75169 45 89128 46 105554 47 124752 48 147263 49 173522 50 204220 51 239939 52 281583 53 329929 54 386147 55 451272 56 526815 57 614150 58 715216 59 831818 60 966455 61 1121503 62 1300152 63 1505493 64 1741623 65 2012554 66 2323512 67 2679687 68 3087729 69 3554341 70 4087960 71 4697203 72 5392771 73 6185687 74 7089496 75 8118258 76 9289085 77 10619859 78 12132156 79 13848648 80 15796466 81 18004322 82 20506251 83 23338467 84 26543648 85 30167353 86 34262958 87 38887669 88 44108101 89 49995923 90 56634161 91 64112355 92 72533801 93 82010173 94 92669716 95 104651415 96 118114292 97 133230928 98 150198130 99 169229869 100 190569283 101 214481124 102 241265371 103 271248948 104 304801357 105 342325701 106 384276332 107 431149387 108 483502832 109 541946238 110 607163738 111 679903199 112 761002146 113 851376626 114 952050657 115 1064144447 116 1188908242 117 1327710070 118 1482074139 119 1653668661 120 1844349544 121 2056148048 122 2291320908 123 2552338237 124 2841940494 125 3163127348 126 3519222680 127 3913864293 128 4351078592 129 4835271866 130 5371315392 131 5964539502 132 6620830877 133 7346629508 134 8149040691 135 9035836068 136 10015581672 137 11097645014 138 12292341823 139 13610949893 140 15065878123 141 16670689204 142 18440293316 143 20390982753 144 22540654430 145 24908858005 146 27517052595 147 30388671972 148 33549419491 149 37027355198 150 40853235301 151 45060624580 152 49686288413 153 54770336318 154 60356673272 155 66493182093 156 73232243747 157 80630964767 158 88751778798 159 97662728551 160 107438159454 161 118159068423 162 129913904627 163 142798995928 164 156919475289 165 172389800247 166 189334822575 167 207890420100 168 228204732735 169 250438925112 170 274768617122 171 301384802042 172 330495499607 173 362326859893 174 397125074742 175 435157697824 176 476715857280 177 522115831191 178 571701605651 179 625846753118 180 684957390918 181 749474411779 182 819876908315 183 896684817523 184 980462880422 185 1071823774333 186 1171432692365 187 1280011042264 188 1398341745565 189 1527273599617 190 1667727404085 191 1820701100650 192 1987276856349 193 2168627105467 194 2366022741841 195 2580840212965 196 2814570987582 197 3068829878528 198 3345365983686 199 3646072432123 200 3972999029376 201 4328363658643 202 4714566886079 203 5134205287969 204 5590088317483 205 6085253859256 206 6622987708036 207 7206841706484 208 7840656226127 209 8528581302371 210 9275102575339 211 10085065885765 212 10963707205253 213 11916681236274 214 12950095925891 215 14070545699283 216 15285151248465 217 16601598107910 218 18028182516667 219 19573856161141 220 21248279009355 221 23061871173845 222 25025873760103 223 27152408925613 224 29454549941738 225 31946390696148 226 34643126322515 227 37561133582568 228 40718063627350 229 44132934884253 230 47826239745912 231 51820051838704 232 56138148670939 233 60806135438327 234 65851585970263 235 71304185514915 236 77195892663506 237 83561103925867 238 90436839668809 239 97862933703583 240 105882246722713 241 114540884553036 242 123888443077253 243 133978259344882 244 144867692496439 245 156618412527940 246 169296722391546 247 182973889854022 248 197726516681664 249 213636919820621 250 230793554364673 251 249291451168557 252 269232701252561 253 290726957916108 254 313891991306661 255 338854264248672 256 365749566870773 257 394723676655355 258 425933084409348 259 459545750448671 260 495741934760834 261 534715062908603 262 576672674947164 263 621837416509613 264 670448123060154 265 722760953690368 266 779050629562159 267 839611730366810 268 904760108316354 269 974834369944623 270 1050197489931101 271 1131238503938604 272 1218374349844323 273 1312051800816207 274 1412749565173446 275 1520980492851169 276 1637293969337159 277 1762278433057267 278 1896564103591580 279 2040825852575069 280 2195786311682500 281 2362219145337709 282 2540952590045690 283 2732873183547533 284 2938929793929549 285 3160137867148989 286 3397584011986765 287 3652430836071049 288 3925922161489404 289 4219388528587092 290 4534253126900878 291 4872038056472080 292 5234371069753666 293 5622992691950603 294 6039763882095503 295 6486674127079084 296 6965850144195823 297 7479565078510576 298 8030248384943036 299 8620496275465021 300 9253082936723584 301 9930972392403497 302 10657331232548835 303 11435542077822100 304 12269218019229455 305 13162217895057700 306 14118662665279993 307 15142952738857192 308 16239786535829651 309 17414180133147291 310 18671488299600356 311 20017426762576943 312 21458096037352875 313 23000006655487335 314 24650106150830486 315 26415807633566314 316 28305020340995997 317 30326181989842962 318 32488293351466646 319 34800954869440826 320 37274405776748063 321 39919565526999987 322 42748078035954688 323 45772358543578024 324 49005643635237860 325 52462044228828635 326 56156602112874285 327 60105349839666540 328 64325374609114542 329 68834885946073846 330 73653287861850323 331 78801255302666613 332 84300815636225113 333 90175434980549617 334 96450110192202756 335 103151466321735321 336 110307860425292752 337 117949491546113970 338 126108517833796349 339 134819180623301516 340 144117936527873820 341 154043597379576026 342 164637479165761032 343 175943559810422749 344 188008647052292972 345 200882556287683151 346 214618299743286295 347 229272286871217148 348 244904537455382394 349 261578907351144123 350 279363328483702140 351 298330063062758068 352 318555973788329072 353 340122810048577426 354 363117512048109997 355 387632532919029219 356 413766180933342356 357 441622981929358429 358 471314064268398776 359 502957566506000018 360 536679070310691097 361 572612058898037556 362 610898403751884097 363 651688879997206953 364 695143713458946028 365 741433159884081680 366 790738119649411311 367 843250788562528425 368 899175348396088339 369 958728697912338039 370 1022141228367345354 371 1089657644424399778 372 1161537834849962838 373 1238057794119125083 374 1319510599727473492 375 1406207446561484046 376 1498478743590581073 377 1596675274490756787 378 1701169427975813509 379 1812356499739472948 380 1930656072350465800 381 2056513475336633801 382 2190401332423765127 383 2332821198543892334 384 2484305294265418164 385 2645418340688763693 386 2816759503217942788 387 2998964447736452188 388 3192707518433532820 389 3398704041358160273 390 3617712763867604407 391 3850538434667429182 392 4098034535626594779 393 4361106170762284110 394 4640713124699623511 395 4937873096788191651 396 5253665124416975145 397 5589233202595404486 398 5945790114707874593 399 6324621482504294317 400 6727090051741041911 401 7154640222653942319 402 7608802843339879261 403 8091200276484465577 404 8603551759348655054 405 9147679068859117592 406 9725512513742021721 407 10339097267123947237 408 10990600063775926978 409 11682316277192317778 410 12416677403151190374 411 13196258966925435698 412 14023788883518847338 413 14902156290309948964 414 15834420884488187758 415 16823822787139235540 416 17873792969689875992 417 18987964267331664553 418 20170183018805933651 419 21424521360255636318 420 22755290216580025235 421 24167053021441363959 422 25664640213837714842 423 27253164546230421733 424 28938037257084798142 425 30724985147095051093 426 32620068617410232181 427 34629700713903575930 428 36760667241831527303 429 39020148000237259657 430 41415739207102358370 431 43955477170518116532 432 46647863284229267971 433 49501890409405150713 434 52527070729108240597 435 55733465144636286648 436 59131714309169618639 437 62733071376043079211 438 66549436566966297359 439 70593393646562135508 440 74878248419470886217 441 79418069346443402231 442 84227730407729499773 443 89322956321353645665 444 94720370257893471808 445 100437544171752847600 446 106493051905239118577 447 112906525199196103350 448 119698712782720205940 449 126891542690981417998 450 134508188001572923822 451 142573136155347404225 452 151112262071917313672 453 160152905244553715581 454 169723951046458040961 455 179855916453958267590 456 190581040442651931018 457 201933379285114688627 458 213948907032733069128 459 226665621435831345557 460 240123655613925192069 461 254365395758574199973 462 269435605212954994455 463 285381555241961986285 464 302253162872576636595 465 320103136152993290536 466 338987127249525432545 467 358963893768162876611 468 380095468763120598459 469 402447339861711475156 470 426088638015652413409 471 451092336355096099860 472 477535459708164115585 473 505499305314204629554 474 535069675351607262117 475 566337121865805599669 476 599397204782301852914 477 634350763653787028577 478 671304203896731807228 479 710369798236628238003 480 751666004194993125567 481 795317798414758232176 482 841457028742823649451 483 890222784951928088286 484 941761789114997698046 485 996228806608573411008 486 1053787078862455346501 487 1114608778936426484246 488 1178875491155735802638 489 1246778716001272919661 490 1318520401612270233211 491 1394313503224447816937 492 1474382572040363953120 493 1558964374994977806169 494 1648308547066172438752 495 1742678277747760981175 496 1842351033503159891456 497 1947619317987658064003 498 2058791472042884901555 499 2176192515439287461623 500 2300165032574323995015 501 2431070104309287327872 502 2569288288377098289277 503 2715220650772245313218 504 2869289850802400662021 505 3031941282464413132738 506 3203644275096202070004 507 3384893356244349844335 508 3576209579998154653665 509 3778141924035171537108 510 3991268758958164118284 511 4216199393504640098478 512 4453575699570940947368 513 4704073821002175842054 514 4968405970488126319771 515 5247322318923878793972 516 5541612982013113936121 517 5852110108921301661036 518 6179690078238084807992 519 6525275806549652788111 520 6889839175409542385632 521 7274403582551733377344 522 7680046623716094332541 523 8107902911527474124144 524 8559167038437716736144 525 9035096690829005915189 526 9537015921990240021534 527 10066318591787500106582 528 10624471981512075020711 529 11213020592521695111577 530 11833590138006300416402 531 12487891737367521803646 532 13177726323474524612296 533 13904989273245567335008 534 14671675272840783232467 535 15479883428970761068955 536 16331822638729701493795 537 17229817230617210720595 538 18176312890390861435030 539 19173882885687454484104 540 20225234604409151266197 541 21333216422211708570596 542 22500824915577356165489 543 23731212437346370138351 544 25027695072821279146408 545 26393760995005382968150 546 27833079238879849385671 547 29349508915133986374839 548 30947108885217475101870 549 32630147920163234060894 550 34403115367205050943148 551 36270732348871285128748 552 38237963520943177237538 553 40310029416409244587118 554 42492419404397720872596 555 44790905293907018009123 556 47211555614160398040332 557 49760750604354432757374 558 52445197947746313627395 559 55271949286085137715951 560 58248417552751868049987 561 61382395164161775318488 562 64682073111542943380450 563 68156060996536236172172 564 71813408056839596203558 565 75663625229609055443633 566 79716708303343130521595 567 83983162210640880002311 568 88474026517495817981245 569 93200902166643654187578 570 98175979536033971312372 571 103412067875563710992444 572 108922626189067392956025 573 114721795630860408658487 574 120824433490320564237117 575 127246148840551966562295 576 134003339931725153597452 577 141113233412529912746556 578 148593925468119890197609 579 156464424966082817448056 580 164744698707340387584228 581 173455718882380096095244 582 182619512839056823919879 583 192259215272078129526273 584 202399122950629095580167 585 213064752104884207160117 586 224282898599046831034627 587 236081701023305130945919 588 248490706844586261413840 589 261540941761240642265706 590 275264982414934173206634 591 289697032618827122974968 592 304873003269975366031773 593 320830596120295386610805 594 337609391590065169560919 595 355250940815002702558179 596 373798862128436852709424 597 393298942187883251157040 598 413799241966727832978019 599 435350207840317348269998 600 458004788008144308553598 601 481818554503286362923737 602 506849831053734861481864 603 533159827070679866278981 604 560812778053476538349414 605 589876092712502332463858 606 620420507127059714307344 607 652520246268116112057162 608 686253193233019826880465 609 721701066553229757379472 610 758949605954969709105713 611 798088766967999186006763 612 839212924798226411060777 613 882421087896683264554173 614 927817121679723721849791 615 975509982873756796925496 616 1025613964982134990453278 617 1078248955392080004474787 618 1133540704665979618906654 619 1191621108583631746910143 620 1252628503530795506440897 621 1316707975853817969920553 622 1384011685831426958558875 623 1454699206941558115141672 624 1528937881135168275063355 625 1606903190858354689128366 626 1688779148601189609516725 627 1774758704783877366657981 628 1865044174831202682776530 629 1959847686321528964669491 630 2059391647140527228529455 631 2163909235608484556362422 632 2273644913597837330081128 633 2388854963699932382735978 634 2509808051552031608082531 635 2636785814481962651219071 636 2770083477684418110395109 637 2910010499193691843303008 638 3056891244979232231862466 639 3211065695545980277248734 640 3372890185488482409685003 641 3542738177508596708707872 642 3721001072479541451508389 643 3908089057205582486668932 644 4104431991606013700457098 645 4310480337124871462076940 646 4526706128254173781044290 647 4753603989138067267826943 648 4991692197319220372390524 649 5241513796775816319683696 650 5503637762499727151307083 651 5778660218961559003723572 652 6067205714919484306343535 653 6369928557132709817142927 654 6687514205661440172553642 655 7020680733548749464953873 656 7370180353811425547662129 657 7736801016790889035132278 658 8121368081058512888507049 659 8524746061205131302394948 660 8947840456000332817673673 661 9391599660555044587641515 662 9857016966290401433259588 663 10345132652677367520056668 664 10857036174895938656583287 665 11393868451739000294452931 666 11956824258286445517629473 667 12547154728067493595502051 668 13166169969647255482980377 669 13815241802783448943206156 670 14495806619536377005379410 671 15209368375944215483241984 672 15957501720133631304230749 673 16741855262985451980947169 674 17564154997755650263621496 675 18426207875324210441995124 676 19329905542049511423199327 677 20277228247502764885900782 678 21270248929688765106878017 679 22311137485682880566295776 680 23402165235974892374954286 681 24545709591163085124246497 682 25744258930034131533263384 683 27000417698448800353553863 684 28316911738879831363625402 685 29696593860867277871605317 686 31142449663120060247020387 687 32657603618448918933404654 688 34245325433219728719773410 689 35909036693513349075724691 690 37652317810725762600765167 691 39478915279883795756623329 692 41392749264546866860893410 693 43397921522754943172592783 694 45498723689129703063649446 695 47699645928878027716139265 696 50005385980149860746062147 697 52420858601901549459658526 698 54951205445179608281719068 699 57601805366500810491218996 700 60378285202834474611028641 701 63286531028521032840985508 702 66332699915362724119980678 703 69523232218023552371152316 704 72864864407855341219969811 705 76364642479247406973532346 706 80029935953661656574123570 707 83868452507581852374822594 708 87888253251761884175130171 709 92097768690318501305952843 710 96505815389469697877049926 711 101121613386982294887579664 712 105954804374756131323439189 713 111015470688345108146850286 714 116314155138696524440183789 715 121861881722882938654960134 716 127670177252209281782740515 717 133751093937700984130081281 718 140117232974725477106760248 719 146781769170263852819573503 720 153758476658245881594406563 721 161061755750279477635534758 722 168706660971164630122439111 723 176708930330666271859881563 724 185085015885255746880625869 725 193852115645795752984189375 726 203028206889569986197651303 727 212632080937520072186590490 728 222683379460186024851577385 729 233202632378520643600875138 730 244211297428606706709925509 731 255731801462210865865001521 732 267787583558210323920375865 733 280403140023083872114273882 734 293604071362025285843562666 735 307417131305664218954016415 736 321870277981032622582593561 737 336992727319136467572139091 738 352815008795455957133215640 739 369369023603738655757458073 740 386688105367749941220651363 741 404807083500032850651734051 742 423762349321394151918928473 743 443591925059596733749014860 744 464335535850798483634138264 745 486034684872448271784326292 746 508732731741838107613602751 747 532474974320122372524707625 748 557308734067567635805394626 749 583283445101886813536239871 750 610450747117966916191771793 751 638864582333908382360557374 752 668581296635294279311393890 753 699659745096778286894322783 754 732161402067670820574405222 755 766150476015982127183457369 756 801694029333610862568750927 757 838862103313805798709299371 758 877727848520950325159242654 759 918367660781873199488134927 760 960861323037560814483873064 761 1005292153304074193879898918 762 1051747159001957690209588879 763 1100317197924192833923669749 764 1151097146124113726578727354 765 1204186073016375022219516980 766 1259687423996378387111229146 767 1317709210896221493178043548 768 1378364210608578997366598367 769 1441770172223648126550509163 770 1508050033038752490738311710 771 1577332143815074048889599018 772 1649750503671651735806603888 773 1725445005022910006140645610 774 1804561688982956164492944638 775 1887253011677361609828822374 776 1973678121921532286407949992 777 2064003150743712843868729628 778 2158401513250589964731360489 779 2257054223353982965849642001 780 2360150221898687182164777942 781 2467886718753771981901721666 782 2580469549453004933593920854 783 2698113546994164480174756365 784 2821042929432312216467202055 785 2949491703928193388274450288 786 3083704087940340693022764495 787 3223934948277725160271634796 788 3370450258759473520427114103 789 3523527577258789108163787096 790 3683456542940343404363084592 791 3850539394533563994343413783 792 4025091510519029370421431009 793 4207441972141088280734057866 794 4397934150197476827913759846 795 4596926316595586652827474178 796 4804792281705797515062559737 797 5021922058584382849328869240 798 5248722555182613689484387806 799 5485618295704258477069984046 800 5733052172321422504456911961 801 5991486228508002426815719531 802 6261402475301701333080509483 803 6543303741858946450905285534 804 6837714561722963378455094373 805 7145182096283051986707103597 806 7466277096963606051213804488 807 7801594907743960700949000439 808 8151756509675604512522473559 809 8517409609130970421571757563 810 8899229771588828461969917942 811 9297921602834531195851268716 812 9714219979529959777862768253 813 10148891331187245215547993860 814 10602734975663191221223594147 815 11076584510377034355391142060 816 11571309261543787320061392659 817 12087815793808125625662163703 818 12627049482760689878061744697 819 13189996152918959195978870018 820 13777683783859651786576215670 821 14391184287298069419105856947 822 15031615358023124634594092716 823 15700142401714084441377203061 824 16397980542787591098996821742 825 17126396715550358417594267009 826 17886711842065410771034749971 827 18680303100276877491522988118 828 19508606286081561360311437656 829 20373118273183778133458320223 830 21275399574724765449983359995 831 22217077010838260632179411309 832 23199846486451169343993151108 833 24225475883821531494697782916 834 25295808074486832813101046417 835 26412764055483014097178757685 836 27578346214889968804237171474 837 28794641731961759722351371975 838 30063826117310982372086476076 839 31388166898835484452139885748 840 32770027459303858556350798568 841 34211871031752548278772284450 842 35716264859093977687647313411 843 37285884524590579748861394566 844 38923518460115987806848673264 845 40632072639400673752129300318 846 42414575463747094337180792087 847 44274182847997609942310578592 848 46214183514849300594196193722 849 48238004505931946889525420996 850 50349216918401212177548479663 851 52551541876147039010384562983 852 54848856745079917639394818811 853 57245201602333536237114022803 854 59744785969613964515539259097 855 62351995821331449988466091700 856 65071400878573831543609957259 857 67907762200418949875852866529 858 70866040084540107092698343080 859 73951402289532005957331751318 860 77169232591877674590168543265 861 80525139690988018278755885197 862 84024966476277979232856334445 863 87674799670795146675673859585 864 91480979866491345649258758071 865 95450111966823518214883921606 866 99589076052990565170686659413 867 103905038690755971019484297570 868 108405464695475636367939373583 869 113098129373644577851404473531 870 117991131259998859170817958823 871 123092905369958432777075796048 872 128412236987976529870072690267 873 133958276013169939669531019310 874 139740551884446204479331410992 875 145768989108216487062234772843 876 152053923412691097170490155911 877 158606118553696417431847045994 878 165436783797931931934295220333 879 172557592110602218633091543836 880 179980699075416049556058362820 881 187718762576041099642814429718 882 195784963269243383580949581143 883 204193025881123335512830178819 884 212957241359090878236182734433 885 222092489913497780851227603378 886 231614264984172822820073009253 887 241538698168481624527315178359 888 251882585148964518765460484658 889 262663412660090356154504995091 890 273899386535208029575034561329 891 285609460876378579895067651913 892 297813368391435715163322531325 893 310531651944349233813920512825 894 323785697366761254448562966667 895 337597767580427105501057917302 896 351991038082228660789452118394 897 366989633845435601723754690827 898 382618667692977386826261193195 899 398904280200653395819254517896 900 415873681190459054784114365403 901 433555192876539531087229255473 902 451978294728708525214023001717 903 471173670120985588372050797991 904 491173254835220446432862090792 905 512010287492584845146484412304 906 533719361988531136324395159447 907 556336482009740068071399064006 908 579899117714618242279047917294 909 604446264662056374189988834749 910 630018505076433611630379753791 911 656658071540248718776792346783 912 684408913209287275550344074993 913 713316764648893234122621625747 914 743429217393715213042975617561 915 774795794337240928934816284891 916 807468027061529837515792402669 917 841499536221802614337232047464 918 876946115104959930393838357555 919 913865816485680423486405066748 920 952319042908502961911588247792 921 992368640529229737341624411920 922 1034079996654109332431762911838 923 1077521141120571341397403386528 924 1122762851668802145076610697751 925 1169878763459173895733432737522 926 1218945482896482311379736998399 927 1270042705928112564209840426890 928 1323253340989653981276400185794 929 1378663636778122744608506419568 930 1436363315039845896899358328017 931 1496445708567209282036578487797 932 1559007904605896258842021462468 933 1624150893881942976244820893251 934 1691979725465930503404211099656 935 1762603667699924360130192603229 936 1836136375421380008668856717508 937 1912696063727159213943851080853 938 1992405688530070149968413761588 939 2075393134169954709485716047151 940 2161791408351324312330912522435 941 2251738844689892053427982289842 942 2345379313161090374436414551550 943 2442862438754801545567295092893 944 2544343828652090726779455860425 945 2649985308251720770267133439295 946 2759955166386673475403099789401 947 2874428410083806869907819978390 948 2993587029233173241168779714720 949 3117620271547411926979127053246 950 3246724928206047105940972859494 951 3381105630594468612010288127859 952 3520975158562887897616477410530 953 3666554760646647127956344306188 954 3818074486705953843294627812023 955 3975773533460423034845675035415 956 4139900603411771887815710365909 957 4310714277666637214536144927321 958 4488483403190813123215639907298 959 4673487495046245204241629451106 960 4866017154182911354694265206385 961 5066374501379277964399166419560 962 5274873627947390097986152243697 963 5491841063841846500452896053576 964 5717616263835974099255567733744 965 5952552112453464578853008309790 966 6197015448369619941842104648878 967 6451387609023188709970129910795 968 6716064996207615136996693074290 969 6991459663439386169435859778902 970 7277999925931103886207676505421 971 7576130994027952290703815097175 972 7886315630998429231248733036401 973 8209034836103596418058528755334 974 8544788553903729460741526714746 975 8894096410797147287955714755070 976 9257498479823236816318777820406 977 9635556074800288403768986034251 978 10028852574908795418824727341738 979 10437994280872373856676062879731 980 10863611303931504965592652844860 981 11306358488849924787366667765401 982 11766916372239763961801564990012 983 12245992177539511607834487453050 984 12744320848028628464246059627674 985 13262666119314202551196742822004 986 13801821632778520931079437719544 987 14362612091531863067120268402220 988 14945894460472306341153073892005 989 15552559212113915719970799358896 990 16183531619906475296861224625003 991 16839773100833956878604913215475 992 17522282609145324707635966077010 993 18232098083140097717852712346111 994 18970297947002453464660671155982 995 19738002669751617842096992232432 996 20536376383452971700767593594009 997 21366628562913781584556907794727 998 22230015769169865076825741905551 999 23127843459154899464880444632242 1000 24061467864032622473692149727975