0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 41 11 56 12 76 13 100 14 133 15 174 16 227 17 293 18 378 19 482 20 614 21 777 22 980 23 1229 24 1538 25 1913 26 2375 27 2936 28 3619 29 4445 30 5447 31 6650 32 8102 33 9844 34 11929 35 14421 36 17397 37 20934 38 25141 39 30130 40 36035 41 43014 42 51253 43 60952 44 72367 45 85771 46 101488 47 119895 48 141425 49 166561 50 195884 51 230040 52 269772 53 315943 54 369532 55 431650 56 503583 57 586791 58 682923 59 793890 60 921840 61 1069219 62 1238818 63 1433809 64 1657751 65 1914745 66 2209382 67 2546876 68 2933129 69 3374832 70 3879476 71 4455617 72 5112818 73 5861910 74 6715073 75 7686068 76 8790271 77 10045137 78 11470120 79 13087189 80 14920926 81 16999024 82 19352342 83 22015721 84 25027942 85 28432606 86 32278351 87 36619765 88 41517576 89 47039990 90 53262821 91 60270971 92 68158908 93 77032274 94 87008375 95 98218426 96 110808008 97 124939594 98 140793545 99 158570897 100 178494456 101 200812562 102 225800242 103 253763475 104 285041190 105 320010048 106 359086742 107 402734213 108 451464253 109 505844631 110 566502995 111 634134925 112 709508608 113 793475010 114 886973280 115 991042536 116 1106829329 117 1235601136 118 1378755262 119 1537835622 120 1714543210 121 1910755624 122 2128540774 123 2370179491 124 2638181908 125 2935315125 126 3264622639 127 3629456600 128 4033502577 129 4480817010 130 4975856768 131 5523524587 132 6129204181 133 6798813283 134 7538847479 135 8356442001 136 9259423945 137 10256386674 138 11356751746 139 12570855993 140 13910027592 141 15386687691 142 17014440872 143 18808196733 144 20784276999 145 22960558009 146 25356600663 147 27993816927 148 30895624034 149 34087642591 150 37597878904 151 41456957053 152 45698338207 153 50358591967 154 55477655872 155 61099156757 156 67270717162 157 74044331573 158 81476732273 159 89629829296 160 98571142165 161 108374319172 162 119119645776 163 130894652165 164 143794717031 165 157923777538 166 173395039802 167 190331814433 168 208868351373 169 229150816294 170 251338277453 171 275603845646 172 302135832822 173 331139089709 174 362836364126 175 397469862416 176 435302848728 177 476621465796 178 521736608285 179 570986053915 180 624736654924 181 683386822440 182 747369097759 183 817153045890 184 893248260594 185 976207743295 186 1066631411082 187 1165170030021 188 1272529318692 189 1389474523305 190 1516835202952 191 1655510560686 192 1806475018673 193 1970784414523 194 2149582505497 195 2344108165379 196 2555702953974 197 2785819486299 198 3036030234252 199 3308037239242 200 3603682356112 201 3924958517297 202 4274021631011 203 4653203655714 204 5065026409176 205 5512216718658 206 5997722456569 207 6524730084803 208 7096683245639 209 7717303088713 210 8390609808531 211 9120946163052 212 9913002432663 213 10771843614479 214 11702938306952 215 12712190162984 216 13805971295290 217 14991158612758 218 16275172458157 219 17666018561745 220 19172332679869 221 20803429038097 222 22569351870620 223 24480931301153 224 26549842847816 225 28788671848395 226 31210982094008 227 33831390102155 228 36665644233601 229 39730710243767 230 43044862471808 231 46627782331491 232 50500663323863 233 54686324409628 234 59209330874352 235 64096124729542 236 69375163795794 237 75077071614740 238 81234797373500 239 87883788212172 240 95062173016533 241 102810960329504 242 111174249520483 243 120199457994746 244 129937563651860 245 140443365664951 246 151775762723841 247 163998052156642 248 177178249147032 249 191389429674184 250 206710096510281 251 223224572285695 252 241023418921502 253 260203887886598 254 280870400714157 255 303135064539444 256 327118222282864 257 352949042749019 258 380766150287359 259 410718299875906 260 442965097501035 261 477677772126994 262 515039999429308 263 555248784266952 264 598515402181783 265 645066407686456 266 695144709998144 267 749010724592527 268 806943601701870 269 869242541049803 270 936228194209609 271 1008244164936892 272 1085658609437174 273 1168865947793597 274 1258288689223088 275 1354379383633733 276 1457622702644310 277 1568537663971922 278 1687680003224171 279 1815644708247836 280 1953068721131109 281 2100633824713178 282 2259069719542029 283 2429157310084586 284 2611732207449986 285 2807688469199308 286 3017982585073825 287 3243637731553928 288 3485748305446104 289 3745484762076722 290 4024098770254092 291 4322928712091618 292 4643405542158092 293 4987059037275222 294 5355524453557209 295 5750549625684301 296 6174002527893853 297 6627879335242960 298 7114313007985486 299 7635582442089459 300 8194122211974457 301 8792532953565987 302 9433592417961274 303 10120267248848403 304 10855725518837120 305 11643350084045289 306 12486752796945391 307 13389789643838184 308 14356576853059535 309 15391508047419010 310 16499272493983071 311 17684874533321321 312 18953654248479599 313 20311309465543561 314 21763919154837503 315 23317968334694571 316 24980374556872192 317 26758516087552046 318 28660261873433582 319 30694003420402626 320 32868688686853856 321 35193858133346185 322 37679683044964704 323 40337006284792427 324 43177385609960754 325 46213139727510416 326 49457397239445796 327 52924148674184299 328 56628301774085191 329 60585740259557307 330 64813386261103641 331 69329266665998735 332 74152583596375762 333 79303789293450441 334 84804665653383912 335 90678408721965826 336 96949718424544440 337 103644893874823327 338 110791934574874671 339 118420647889278835 340 126562763146236603 341 135252052793736482 342 144524461007519947 343 154418240229595862 344 164974096084630058 345 176235341207917194 346 188248058489178106 347 201061274328716441 348 214727142472197094 349 229301139090962426 350 244842269745166969 351 261413288973359374 352 279080933225544447 353 297916167970637527 354 317994449782611433 355 339396004333921124 356 362206121199905705 357 386515466509622301 358 412420414458248868 359 440023398837632607 360 469433285722437474 361 500765768603864961 362 534143787247128811 363 569697971713241991 364 607567112976599883 365 647898661746754118 366 690849257096731756 367 736585286693738652 368 785283480427700869 369 837131539439645266 370 892328802561274107 371 951086952399945441 372 1013630763318387566 373 1080198893802468816 374 1151044725734450726 375 1226437253350546626 376 1306662024699630318 377 1392022138702676854 378 1482839300960260025 379 1579454941765324297 380 1682231399839886365 381 1791553175647473414 382 1907828258214217178 383 2031489529752797333 384 2162996252479852486 385 2302835642413877889 386 2451524535057359555 387 2609611148294476207 388 2777676947979996520 389 2956338622159797293 390 3146250170030935882 391 3348105112259714986 392 3562638829473184066 393 3790631036291874949 394 4032908398507016299 395 4290347301607218409 396 4563876779129294215 397 4854481609969432656 398 5163205594102832032 399 5491155016877706682 400 5839502312414741995 401 6209489937426649075 402 6602434467187129218 403 7019730926240757983 404 7462857366919614893 405 7933379709670440098 406 8432956859743856145 407 8963346115822929291 408 9526408886786646214 409 10124116733933368923 410 10758557756691169810 411 11431943341073511718 412 12146615290941395664 413 12905053363482018382 414 13709883231216059420 415 14563884894331955618 416 15470001568163735066 417 16431349072252737425 418 17451225748589681068 419 18533122938414411634 420 19680736048245617533 421 20897976237775859201 422 22188982763722680746 423 23558136015874893953 424 25010071283216575187 425 26549693290370165822 426 28182191546435888523 427 29913056550905820075 428 31748096903387243177 429 33693457366720528410 430 35755637935388718296 431 37941513964248822439 432 40258357415191674806 433 42713859282792681112 434 45316153262894186508 435 48073840731851474641 436 50996017107399452409 437 54092299666266615840 438 57372856897251003131 439 60848439473072398349 440 64530412928314013942 441 68430792135818087729 442 72562277678367698933 443 76938294218045233804 444 81573030970621125521 445 86481484398458106713 446 91679503240937252742 447 97183836008150642704 448 103012181069759297507 449 109183239478332739601 450 115716770673313481171 451 122633651219932457100 452 129955936744983496888 453 137706927240362407042 454 145911235913710517494 455 154594861775409341220 456 163785266160518929322 457 173511453395179798244 458 183804055827363610882 459 194695423453877595689 460 206219718387038528003 461 218413014417668400964 462 231313401943805779023 463 244961098549124089295 464 259398565529162610537 465 274670630679536365285 466 290824617675942641667 467 307910482393468378197 468 325980956530011900928 469 345091698918133208098 470 365301454928800286404 471 386672224391957041127 472 409269438480050227570 473 433162146024282259163 474 458423209756795521690 475 485129512998040188734 476 513362177334488308460 477 543206791860518492100 478 574753654586958728220 479 608098026650332937396 480 643340399988504931007 481 680586779183188790842 482 719948978204750237820 483 761544932832988379499 484 805499029566217017336 485 851942451873089119740 486 901013544684230220808 487 952858198067149979207 488 1007630251074940359706 489 1065491916810322350320 490 1126614229798539542784 491 1191177516818787314472 492 1259371892401132191463 493 1331397780257752452754 494 1407466461980485292248 495 1487800654404730647854 496 1572635117109433423245 497 1662217291597759542464 498 1756807973779854160328 499 1856682021461512241476 500 1962129098627201315534 501 2073454458396542792136 502 2190979766626628738592 503 2315043968232284655722 504 2446004198399105267067 505 2584236740973833307492 506 2730138036429780800278 507 2884125741925652100565 508 3046639846100750531245 509 3218143841382234143210 510 3399125956717252839935 511 3590100453788741342681 512 3791608989924624089426 513 4004222051070601564844 514 4228540458362899132490 515 4465196952013698398203 516 4714857856404814798668 517 4978224830479066785502 518 5256036707719926753039 519 5549071430223083199905 520 5858148081584842803937 521 6184129023566407449038 522 6527922141736379388959 523 6890483205551138731847 524 7272818348600264890420 525 7675986675026793507655 526 8101102998426263704218 527 8549340719838964005860 528 9021934851773056588699 529 9520185195537318617380 530 10045459679517490974798 531 10599197866404728742428 532 11182914637775054973621 533 11798204064829951574212 534 12446743474537053221975 535 13130297720861497319199 536 13850723671249503096906 537 14609974919021445716292 538 15410106732849052230328 539 16253281255035444502780 540 17141772960884769822272 541 18077974392045405305352 542 19064402177334318121869 543 20103703355205500296000 544 21198662012710000603429 545 22352206256514130182461 546 23567415532293710015520 547 24847528309611194867824 548 26195950150206929229747 549 27616262178501173639548 550 29112229974008178025663 551 30687812906312732657764 552 32347173934251946974715 553 34094689891986019046811 554 35934962285730175786497 555 37872828626061375193512 556 39913374321907125588938 557 42061945163575191963473 558 44324160423491860529108 559 46705926604688401426566 560 49213451868510393125378 561 51853261174528288255715 562 54632212167200805305629 563 57557511845490726498959 564 60636734053356889204951 565 63877837830852183663449 566 67289186667446903893523 567 70879568701175501240030 568 74658217909275359262252 569 78634836338153923346194 570 82819617422788885966962 571 87223270448040760135371 572 91857046206841999549367 573 96732763912827510585308 574 101862839427693129763925 575 107260314866416651784305 576 112938889646456508184060 577 118912953050161827257252 578 125197618372891190731070 579 131808758732751620898259 580 138763044621442569813985 581 146077983279427156102276 582 153771959982564314170763 583 161864281331426527713731 584 170375220638808989932938 585 179326065515413102601897 586 188739167758372681339849 587 198637995652190321582080 588 209047188796778258972044 589 219992615582658479166533 590 231501433438986137016872 591 243602151985924423561115 592 256324699229035569218758 593 269700490939767083417829 594 283762503372824411658871 595 298545349478236942930131 596 314085358773265109589653 597 330420661046968407843865 598 347591274078281818198402 599 365639195556837058988578 600 384608499404542297883564 601 404545436705105876672602 602 425498541458285288883258 603 447518741385668927050987 604 470659474025287572321098 605 494976808363311648955888 606 520529572262554808562331 607 547379485959481831711533 608 575591301913947745527203 609 605232951308983363117109 610 636375697511633152232352 611 669094296820152037106895 612 703467166837825563570997 613 739576562829301674836942 614 777508762431662789174598 615 817354259109533584032663 616 859207964761368909045591 617 903169421902707105396410 618 949343025871667893032938 619 997838257522332086750528 620 1048769926892928403443050 621 1102258428357982865164416 622 1158430007796831113981358 623 1217417042335165872857438 624 1279358333241669559908289 625 1344399412588280418399124 626 1412692864310343947471396 627 1484398660331826309195132 628 1559684512451005403800809 629 1638726240713625506427079 630 1721708159033503389482182 631 1808823478855027685073007 632 1900274731688006811548059 633 1996274211382916457584797 634 2097044437053893387483568 635 2202818637597841885546443 636 2313841258800890428733312 637 2430368494068186723636257 638 2552668839859786247822871 639 2681023676964203822303662 640 2815727878792209088749734 641 2957090447926688255509594 642 3105435182220028037100873 643 3261101371788541686244650 644 3424444528314125026495322 645 3595837148126645467086237 646 3775669510606718024817211 647 3964350513517555974556225 648 4162308546946704157253764 649 4369992407613723641289208 650 4587872255378516373532894 651 4816440613867017572466505 652 5056213417216679784596681 653 5307731105033590972622939 654 5571559767746466695035147 655 5848292344640207711280436 656 6138549876953494764046986 657 6442982818531084990769226 658 6762272406632378266625690 659 7097132095613527630291099 660 7448309056321198401621895 661 7816585744162138583305261 662 8202781538944354657101771 663 8607754459723006760829351 664 9032402958027520302665620 665 9477667792995983054880473 666 9944533992099062053802682 667 10434032901298574867697636 668 10947244328655918785381158 669 11485298785582956866677384 670 12049379830113151077088728 671 12640726516763892678906268 672 13260635957762614949203693 673 13910466000619576884081723 674 14591638027249722076612792 675 15305639880074959501656552 676 16054028920777169986259024 677 16838435227621449486883193 678 17660564937529191236577185 679 18522203739351846671162188 680 19425220525079269526692806 681 20371571206011730226919022 682 21363302701232723265738368 683 22402557106040898381073785 684 23491576048334618636942241 685 24632705241292140704130533 686 25828399241055074674732338 687 27081226418503005631837039 688 28393874154603865106792409 689 29769154269238258053819336 690 31210008693827469453011629 691 32719515398544771601214291 692 34300894585358991129632535 693 35957515158648600334292581 694 37692901485635017828925783 695 39510740459415915366661219 696 41414888877934367089667747 697 43409381152798282010426293 698 45498437362468058183219651 699 47686471664959489505241607 700 49978101085865076824591432 701 52378154698180811802172764 702 54891683211138759134938731 703 57523968985989207200990197 704 60280536497451448501657373 705 63167163260360319949727130 706 66189891241878269986206335 707 69355038780520941973756702 708 72669213034160000766605318 709 76139322980121301411316156 710 79772592991491579594701402 711 83576577014783860884292933 712 87559173375192977692206730 713 91728640236799290817368843 714 96093611746253347206287352 715 100663114889698240851691105 716 105446587093962471695538998 717 110453894604385732136982655 718 115695351673026088593168111 719 121181740592441228242204234 720 126924332611741821351606536 721 132934909773183539165437980 722 139225787709199106456359704 723 145809839441475069548649774 724 152700520225453219938047809 725 159911893485486134907973523 726 167458657887803845482364505 727 175356175600456741326930618 728 183620501791492522920255730 729 192268415418805069476541368 730 201317451367364875970059813 731 210785933991907227355939964 732 220693012125620230535579886 733 231058695617943497795810502 734 241903893467264735169911167 735 253250453617089318050990953 736 265121204487162597692207915 737 277539998314050076865130689 738 290531756378832607809225018 739 304122516202856659607139607 740 318339480795899811135623554 741 333211070044673592492516108 742 348766974333296454857034912 743 365038210491234047564968892 744 382057180168229484503703025 745 399857730739938398354183513 746 418475218852350236519927853 747 437946576717624446014878913 748 458310381278706472849801156 749 479606926365020387354854845 750 501878297966671650677869662 751 525168452759942164910672778 752 549523300022430216220383255 753 574990787081987958461028136 754 601620988449649386713475315 755 629466198793030716612472218 756 658581029913234239441095316 757 689022511895105206939072982 758 720850198607791521993357133 759 754126277739947911152272332 760 788915685561623211594552125 761 825286226612882211365262373 762 863308698527556556371019291 763 903057022209204315651218462 764 944608377585400406292766300 765 988043345175892969343211727 766 1033446053719960701057712753 767 1080904334118506914127282291 768 1130509879957045775336102097 769 1182358414886789769242484240 770 1236549867152554406491220819 771 1293188551568172846510658452 772 1352383359252580391004764719 773 1414247955452704422859891688 774 1478900985792801896899957571 775 1546466291303943145103514654 776 1617073132601971863421367518 777 1690856423597497541378286761 778 1767956975137324502811829871 779 1848521748993213737622652553 780 1932704122631038082012822336 781 2020664165211252556210533765 782 2112568925290190237628744547 783 2208592730711036505112966875 784 2308917501193463655551122065 785 2413733074151852555219719356 786 2523237544293823514041859819 787 2637637617573476171082317153 788 2757148980097335955185034564 789 2881996682605556453438936498 790 3012415541176473853769975906 791 3148650554829188146692334593 792 3290957340726500236656698831 793 3439602587709304202961388344 794 3594864528923467344901556504 795 3757033434331370315513212875 796 3926412123932676987733314235 797 4103316502552605214887482715 798 4288076117091030728247303614 799 4481034737162227421156527476 800 4682550960092987864753029325 801 4892998841286332598873082875 802 5112768550999069848000576933 803 5342267058624167803792464257 804 5581918845613318785037791636 805 5832166648221272264622968770 806 6093472231301566585271782133 807 6366317194433266231062143951 808 6651203811710293224420718961 809 6948655906579002260386364062 810 7259219763165876249522641560 811 7583465075595692806494460532 812 7921985936861326262521386512 813 8275401868869591361913888141 814 8644358895353304541022413288 815 9029530659408131021512634560 816 9431619587483909282659349412 817 9851358101734100923286659339 818 10289509882703920249621886297 819 10746871184417664509597999607 820 11224272204008918352114361510 821 11722578508123764091305681729 822 12242692518417028243302524223 823 12785555058555063482033460385 824 13352146965235749620809459921 825 13943490765837436749752755992 826 14560652425413605530780395920 827 15204743165859234316568746273 828 15876921360188409646850035979 829 16578394504980758316242879073 830 17310421274176998076892101419 831 18074313657531475682619114839 832 18871439187162181968916581879 833 19703223255776593542133879223 834 20571151530295001146205866375 835 21476772464741950581251707681 836 22421699916431271171609603007 837 23407615869631120224575897149 838 24436273271062775273847191126 839 25509498981760797710888252371 840 26629196850002936165541919527 841 27797350910205993218714291562 842 29016028712879129518811086680 843 30287384790929003061786737878 844 31613664267822045008218505950 845 32997206613328356845756661535 846 34440449552799507257311076487 847 35945933136169234349635532935 848 37516303973112075555685809051 849 39154319641050602712584748051 850 40862853272967616478421055696 851 42644898332255729023629039918 852 44503573582123649132992559537 853 46442128257376585783051817435 854 48463947446697948797356026033 855 50572557693881386550618747619 856 52771632826796638806959829508 857 55065000023220170193152360127 858 57456646123022601028584311522 859 59950724196580076865203866276 860 62551560379666469953987861646 861 65263660985488234419872923389 862 68091719904944438392064014789 863 71040626306631563045049343398 864 74115472648566732209395350092 865 77321563014074755494730360391 866 80664421784774423432828314952 867 84149802664108573326223640033 868 87783698065391292718185397417 869 91572348878894985506894913693 870 95522254633070693839766003414 871 99640184065587846534028148756 872 103933186120495352918869771807 873 108408601388445541201696159621 874 113074074007586779369596991951 875 117937564043420642459414807194 876 123007360366636199917415234829 877 128292094048678390799577029683 878 133800752295580605644956364958 879 139542692941394579350052055129 880 145527659523384673751279834378 881 151765796962019752335221253585 882 158267667869695364664015491854 883 165044269513053114668221705712 884 172107051454734221213927542895 885 179467933901411737462817454897 886 187139326785992115156506048537 887 195134149612963230671955799552 888 203465852096994178064055238991 889 212148435626063641302019415400 890 221196475581610147065369667231 891 230625144549460651483283348582 892 240450236456605518503535109262 893 250688191670249813526437473716 894 261356123096984888207361102337 895 272471843321392418768966026479 896 284053892824917450720548034949 897 296121569327429694261091634266 898 308694958295535533054054560548 899 321794964663409211165077509820 900 335443345813682842825393038238 901 349662745867773676082481804068 902 364476731336936008699111419417 903 379909828187306916567901242301 904 395987560374272279667441332403 905 412736489903615290611443330047 906 430184258479126682626074519662 907 448359630798657343471611791772 908 467292539562982989532260840403 909 487014132264330415809444640957 910 507556819823988953410949246661 911 528954327151102658791883694656 912 551241745697512127212983659739 913 574455588086393434344085233965 914 598633844895429540642269920696 915 623816043678350595723356154452 916 650043310311898228374840381857 917 677358432758609460817276423588 918 705805927339282937223457190567 919 735432107612588394013664729662 920 766285155963014660496311065234 921 798415198002227004015322939624 922 831874379892926630435848934032 923 866716948708479038982553809380 924 902999335945909412964375493575 925 940780244314358132965061330953 926 980120737925753954882937296735 927 1021084336019302667824455858210 928 1063737110356411721503319678800 929 1108147786427883125661008848397 930 1154387848620614950872236971034 931 1202531649496663242207175694765 932 1252656523343338696888351143519 933 1304842904159053837869822181075 934 1359174448245904804947311333000 935 1415738161586475649291166819326 936 1474624532189100930875483600789 937 1535927667592823472134167655601 938 1599745437730547741341974323586 939 1666179623356425187870870918805 940 1735336070251326053993738101835 941 1807324849428363126875885060842 942 1882260423568847445697382448749 943 1960261819927785298638164641431 944 2041452809957081613915954841652 945 2125962095904009054593425684076 946 2213923504652247314115618485728 947 2305476189082906155855965029894 948 2400764837243432118535210373647 949 2499939889623176354075364353292 950 2603157764845684243566417394720 951 2710581094099471110772650196894 952 2822378964641188057294159064708 953 2938727172717673640572542550935 954 3059808486266447487436109879642 955 3185812917767748125220761310528 956 3316938007635267230733654049961 957 3453389118547304555930936714336 958 3595379741135181217968345303516 959 3743131811461423612065961749459 960 3896876040736486562731659734114 961 4056852257739643703846192751314 962 4223309764427157632324284738453 963 4396507705228974910868440732100 964 4576715450553995291644963724751 965 4764212995043465071286826592921 966 4959291371132266802799366588197 967 5162253078498847960194431027499 968 5373412530006276983002030894287 969 5593096514759464631003895953917 970 5821644678926971168120262444097 971 6059410025000065851315190591729 972 6306759430186846091770970998708 973 6564074184665291986980387124058 974 6831750550446161567831022512968 975 7110200341624657953038231531248 976 7399851526828858003389386063609 977 7701148854703020464320429407217 978 8014554503295128979668496580736 979 8340548754250411936418866749860 980 8679630692746158706545118975588 981 9032318934137963609830301629767 982 9399152378323619727129287718807 983 9780690992868300818417353682972 984 10177516625973459209332027031295 985 10590233850412080251882885423227 986 11019470839594621508366286404913 987 11465880276973180419797440895277 988 11930140300036233325918780722608 989 12412955480192728449880745182667 990 12915057839892455296714671294204 991 13437207908379514145974194883222 992 13980195817527435708579931911826 993 14544842439258118327858146636946 994 15132000566102326721219373748847 995 15742556136517102719634220950243 996 16377429506635148107009591745541 997 17037576770183128147006659089298 998 17723991128369990358515778708815 999 18437704311612877703785263654772 1000 19179788055037122920465786859682