0 1 1 1 2 1 3 3 4 3 5 5 6 8 7 10 8 13 9 20 10 26 11 33 12 46 13 58 14 75 15 101 16 125 17 157 18 206 19 253 20 317 21 403 22 494 23 608 24 760 25 926 26 1131 27 1393 28 1685 29 2038 30 2487 31 2985 32 3585 33 4331 34 5168 35 6172 36 7392 37 8771 38 10410 39 12382 40 14622 41 17258 42 20400 43 23975 44 28159 45 33115 46 38739 47 45298 48 53000 49 61759 50 71921 51 83775 52 97249 53 112817 54 130879 55 151411 56 175020 57 202293 58 233243 59 268734 60 309561 61 355823 62 408695 63 469297 64 537873 65 616042 66 705291 67 806155 68 920810 69 1051322 70 1198610 71 1365585 72 1555125 73 1768693 74 2010243 75 2283746 76 2591414 77 2938641 78 3330820 79 3771337 80 4267499 81 4826570 82 5453630 83 6158487 84 6951081 85 7838764 86 8834674 87 9952336 88 11202300 89 12602181 90 14170331 91 15921551 92 17879566 93 20069030 94 22510788 95 25236554 96 28279402 97 31668325 98 35445661 99 39655745 100 44338660 101 49550543 102 55350864 103 61794386 104 68955832 105 76914433 106 85744620 107 95545508 108 106422477 109 118476242 110 131837998 111 146647197 112 163039728 113 181188521 114 201278183 115 223490791 116 248053841 117 275210993 118 305205146 119 338335204 120 374921838 121 415287500 122 459824217 123 508952716 124 563100064 125 622778891 126 688539772 127 760946251 128 840667143 129 928421706 130 1024950878 131 1131125046 132 1247881735 133 1376191824 134 1517186214 135 1672083897 136 1842152769 137 2028859430 138 2233784864 139 2458581028 140 2705145337 141 2975523611 142 3271862267 143 3596611004 144 3952412066 145 4342046830 146 4768670950 147 5235690414 148 5746699452 149 6305756614 150 6917242398 151 7585790173 152 8316609313 153 9115322400 154 9987889220 155 10940983392 156 11981806458 157 13118007979 158 14358120350 159 15711351800 160 17187497855 161 18797447642 162 20552952611 163 22466530143 164 24552052677 165 26824489858 166 29299803147 167 31995635621 168 34931020473 169 38126273448 170 41603792622 171 45387735078 172 49503908708 173 53980699953 174 58848717603 175 64140685346 176 69892516967 177 76142932061 178 82933346711 179 90309127141 180 98319169752 181 107015799524 182 116456231104 183 126702112097 184 137819438593 185 149880254006 186 162962157251 187 177148249967 188 192529105493 189 209202253739 190 227272163040 191 246852529498 192 268065746344 193 291042933399 194 315926604008 195 342870122157 196 372037801366 197 403608016870 198 437772657764 199 474737326945 200 514724964263 201 557975314783 202 604745267137 203 655313066456 204 709977831866 205 769060063756 206 832906552080 207 901889979568 208 976409642927 209 1056897182667 210 1143816306112 211 1237663786255 212 1338976163391 213 1448329630867 214 1566341403842 215 1693677540762 216 1831053071685 217 1979233836785 218 2139045617328 219 2311374601639 220 2497169805076 221 2697453739742 222 2913323344697 223 3145953117187 224 3396607612494 225 3666642955818 226 3957510880620 227 4270773378220 228 4608104965043 229 4971297855231 230 5362279129726 231 5783113973918 232 6236012277557 233 6723348745632 234 7247667404743 235 7811689929592 236 8418339243420 237 9070745627159 238 9772257173698 239 10526467506833 240 11337223895489 241 12208640321585 242 13145130083705 243 14151416388144 244 15232548661497 245 16393940873818 246 17641385246294 247 18981072531803 248 20419637086067 249 21964174454210 250 23622266477410 251 25402034333156 252 27312160949301 253 29361921952736 254 31561248172904 255 33920753945447 256 36451775204884 257 39166443172081 258 42077719885761 259 45199444988219 260 48546422606864 261 52134465746339 262 55980453647508 263 60102434228748 264 64519679358211 265 69252754947112 266 74323641832538 267 79755804317882 268 85574275644395 269 91805800715723 270 98478920736250 271 105624077258907 272 113273780785520 273 121462714901885 274 130227862776542 275 139608706306579 276 149647353912619 277 160388694089176 278 171880630655784 279 184174239219889 280 197323953191010 281 211387841777338 282 226427801100305 283 242509779155460 284 259704104441996 285 278085718774787 286 297734449008777 287 318735395606206 288 341179215591161 289 365162450393591 290 390787985219326 291 418165392337808 292 447411326140593 293 478650066205705 294 512013933084325 295 547643763664882 296 585689553236962 297 626310958266392 298 669677867632673 299 715971161845525 300 765383319860958 301 818119104844224 302 874396461881522 303 934447249216241 304 998518060659431 305 1066871286876474 306 1139785995314389 307 1217558915529780 308 1300505693610668 309 1388961949725464 310 1483284457234046 311 1583852625328576 312 1691069768387159 313 1805364515557049 314 1927192562929335 315 2057038195097698 316 2195415968683592 317 2342872782784395 318 2499989700512079 319 2667383958054266 320 2845711410434465 321 3035668709861239 322 3237995701103972 323 3453478309917082 324 3682951145320371 325 3927300352929062 326 4187467025359369 327 4464450307814607 328 4759310793840292 329 5073174551226273 330 5407236824148930 331 5762766071357516 332 6141108717283251 333 6543693560988608 334 6972036574551918 335 7427746508168521 336 7912530135946833 337 8428197953286604 338 8976670787161717 339 9559986032227370 340 10180304410020953 341 10839917762386987 342 11541256458286800 343 12286897406655283 344 13079573241728360 345 13922181112566485 346 14817792175187685 347 15769662414793705 348 16781243067182045 349 17856191855538650 350 18998385736173164 351 20211933245130678 352 21501187790960986 353 22870762660155257 354 24325545633317902 355 25870714698933298 356 27511755712518031 357 29254479686524369 358 31105041353162679 359 33069959938939601 360 35156139601579751 361 37370891344246751 362 39721957445458065 363 42217535598113381 364 44866304763606272 365 47677453888316845 366 50660710395324892 367 53826370667450145 368 57185333788391762 369 60749135149095401 370 64529982365250241 371 68540794906294007 372 72795243707764834 373 77307793465677712 374 82093749161857333 375 87169302724027541 376 92551582799211473 377 98258709352784513 378 104309848594094921 379 110725271516848520 380 117526417945148196 381 124735961147931113 382 132377876650145317 383 140477517328009822 384 149061689374342740 385 158158733134751203 386 167798611121090539 387 178012997267061904 388 188835371836122543 389 200301124531639353 390 212447659303876549 391 225314505716732750 392 238943439692369505 393 253378606505730974 394 268666651392477750 395 284856860881956579 396 302001307051961209 397 320155000618357275 398 339376056295073386 399 359725861887760014 400 381269257636931675 401 404074729606309115 402 428214607781133356 403 453765276054211464 404 480807398296492003 405 509426150305184555 406 539711465539664222 407 571758299283321459 408 605666900076908313 409 641543097141681044 410 679498608916284557 411 719651360526579511 412 762125819795876413 413 807053357454763516 414 854572618259938036 415 904829913603862920 416 957979641871574212 417 1014184722048076804 418 1073617052230975182 419 1136457999967526090 420 1202898908610252852 421 1273141632530050835 422 1347399108839612364 423 1425895948400931242 424 1508869060265108254 425 1596568318004077804 426 1689257249177509945 427 1787213763521945445 428 1890730929215820629 429 2000117776811608439 430 2115700148004229267 431 2237821599583887574 432 2366844340380138328 433 2503150220106377789 434 2647141781561753307 435 2799243352064998660 436 2959902194954753972 437 3129589733839211626 438 3308802823386913349 439 3498065089618421951 440 3697928353738540565 441 3908974111062312741 442 4131815090337449883 443 4367096909005468384 444 4615499793553974017 445 4877740392838580854 446 5154573701594868648 447 5446795060708709692 448 5755242264965343212 449 6080797797365987251 450 6424391153802757260 451 6787001291953745449 452 7169659225563739468 453 7573450724919926353 454 7999519160860822396 455 8449068515784231896 456 8923366519282979078 457 9423747949580075116 458 9951618126788960827 459 10508456552233363299 460 11095820739226874371 461 11715350264195271032 462 12368770988753500273 463 13057899502805064515 464 13784647820739823856 465 14551028277472588376 466 15359158679562176334 467 16211267747039694006 468 17109700788573560304 469 18056925670936464956 470 19055539122356917562 471 20108273308025979987 472 21218002745055891484 473 22387751600879743971 474 23620701308761237623 475 24920198574705917940 476 26289763824695821192 477 27733100021051242805 478 29254101929953526618 479 30856865894568177602 480 32545700037437779893 481 34325134982766333399 482 36199935159195433357 483 38175110601345068989 484 40255929350268920076 485 42447930520298223476 486 44756937944913537662 487 47189074512350952784 488 49750777266101549965 489 52448813177080818298 490 55290295709869405222 491 58282702266798842332 492 61433892410567108681 493 64752127000757160912 494 68246088337689936505 495 71924901207987034359 496 75798154981633906663 497 79875926864785626089 498 84168806196200988489 499 88687919953123472477 500 93444959582947134880 501 98452209041947025138 502 103722574224693227232 503 109269613914042801089 504 115107572126311485045 505 121251412055015308531 506 127716851758299731724 507 134520401457950705526 508 141679402675359491400 509 149212069366658311983 510 157137530918243141884 511 165475877252540130778 512 174248206225414283868 513 183476673169897203682 514 193184542863362805046 515 203396244121069430371 516 214137426864481064979 517 225435021971864892805 518 237317304138246344849 519 249813957587285544613 520 262956144976382398799 521 276776579749275226041 522 291309601773388386093 523 306591256640923571234 524 322659378918534390425 525 339553679178256374820 526 357315835230743139222 527 375989587880022669571 528 395620841028820788530 529 416257766602457544157 530 437950914649160060558 531 460753328443492911096 532 484720665113305846720 533 509911322191505071761 534 536386569918582753973 535 564210689874790201051 536 593451120392206122597 537 624178608573795304257 538 656467369563665406716 539 690395253573912084799 540 726043920498632218563 541 763499022832368506379 542 802850397460440604872 543 844192266158093252677 544 887623445597430116745 545 933247567499466083850 546 981173308778066452441 547 1031514632566125224072 548 1084391040840016659831 549 1139927838503111079027 550 1198256409920909574995 551 1259514508712570663685 552 1323846560678549110769 553 1391403980971301808203 554 1462345506413869664343 555 1536837542870798850028 556 1615054528906495305740 557 1697179316748575228243 558 1783403570492289649016 559 1873928182924702915418 560 1968963712113244494612 561 2068730837734504373498 562 2173460838682805084745 563 2283396093246431267459 564 2398790601876727499435 565 2519910534269848860963 566 2647034802210648246233 567 2780455658264370095635 568 2920479322238000005969 569 3067426637043076522771 570 3221633754118996745192 571 3383452850565360078155 572 3553252879820765376374 573 3731420356135535629713 574 3918360175241258761370 575 4114496473286446056758 576 4320273524391791480362 577 4536156679513301178020 578 4762633348944159169263 579 5000214028935182749383 580 5249433375442353522010 581 5510851327627477467773 582 5785054281741625346881 583 6072656318759311160972 584 6374300488722555360620 585 6690660152601314371407 586 7022440385441935896902 587 7370379444138593884356 588 7735250300842202070312 589 8117862246231930427307 590 8519062566408216652134 591 8939738294665828095735 592 9380818042881415624124 593 9843273916752787042230 594 10328123516433893835952 595 10836432027872098049011 596 11369314409624763624231 597 11927937677032025435674 598 12513523289695129164370 599 13127349647646574592912 600 13770754698476079147324 601 14445138662084284450177 602 15151966879137745930584 603 15892772785938683890394 604 16669161023193582876307 605 17482810685529571182705 606 18335478714992940206699 607 19229003446926790741544 608 20165308315951543078370 609 21146405725885194120651 610 22174401093026470986732 611 23251497071511718858850 612 24379997965278024369391 613 25562314337209415460215 614 26800967825290673988056 615 28098596171103066643085 616 29457958472536174813575 617 30881940671796658864928 618 32373561284971234003147 619 33935977386476972760551 620 35572490860896762559632 621 37286554929518420315604 622 39081780966551145673354 623 40961945619115377678867 624 42930998239543165777988 625 44993068646807557523266 626 47152475232979796610805 627 49413733424648934259834 628 51781564518197062559748 629 54260904906862112367200 630 56856915711123629368639 631 59574992833638248975809 632 62420777458949420407722 633 65400167011338736686606 634 68519326594670194992412 635 71784700937036754296115 636 75203026855671230844706 637 78781346268924626044359 638 82527019781035389194051 639 86447740857544473371357 640 90551550621478923854904 641 94846853299312791037541 642 99342432337291018968681 643 104047467221972493306357 644 108971551037704302936273 645 114124708784726675899917 646 119517416495963843835852 647 125160621189386488745822 648 131065761683193236112447 649 137244790316588961060048 650 143710195617748600494046 651 150475025950253938982954 652 157552914186091912471516 653 164958103452102215348275 654 172705473985758636681370 655 180810571154344551233619 656 189289634690380662429320 657 198159629184416203241812 658 207438275895959232060106 659 217144085942129609541422 660 227296394911084884898471 661 237915398968545648783440 662 249022192524578820130288 663 260638807514433394035859 664 272788254370245298031100 665 285494564759299941955406 666 298782836150301724064149 667 312679278294012080643977 668 327211261703549426940524 669 342407368204483205183222 670 358297443651813618147579 671 374912652909943928257188 672 392285537175621168632274 673 410450073752998178858184 674 429441738389096460047233 675 449297570260799043748371 676 470056239736083565604428 677 491758119031474911165264 678 514445355869477993912385 679 538161950273937979901599 680 562953834640723660927370 681 588868957201793207307502 682 615957369037712742758452 683 644271314793368747032471 684 673865327231111995187729 685 704796325795643787162923 686 737123719364898709349374 687 770909513339458106136631 688 806218421266422482131744 689 843117981193945410696712 690 881678676929645757251201 691 921974064423112537901260 692 964080903493387923834922 693 1008079295098015459488987 694 1054052824391148918609575 695 1102088709819360650029436 696 1152277958478133563438589 697 1204715528007173304159865 698 1259500495304380562270898 699 1316736232311271376031692 700 1376530589182392759361428 701 1438996085153645449060351 702 1504250107395938112777490 703 1572415118205360009328257 704 1643618870884200131263494 705 1717994634637184607906862 706 1795681428877503049319693 707 1876824267341242303018712 708 1961574412377395261125756 709 2050089639856718909439073 710 2142534515147818984654220 711 2239080680575876054356951 712 2339907154861955102422719 713 2445200645047169299140355 714 2555155871371486764360237 715 2669975905666476370044804 716 2789872523829037591219084 717 2915066572907160333785391 718 3045788353425859830730947 719 3182278017590821596206881 720 3324785983969791039094138 721 3473573369357102568418415 722 3628912438538022852048382 723 3791087072630614223138016 724 3960393256797176254344262 725 4137139588130775057628358 726 4321647804481986852020576 727 4514253335115122542756256 728 4715305874099144238466974 729 4925169977296762929751529 730 5144225683950005585663364 731 5372869163879341141697023 732 5611513391270494837093228 733 5860588846169491510200773 734 6120544244828538414447861 735 6391847300001290024016456 736 6674985512445105365517041 737 6970466994913709889144073 738 7278821329878665044644994 739 7600600462390916171057268 740 7936379629523744877047952 741 8286758327792712115947614 742 8652361320136093767437467 743 9033839684074211323073711 744 9431871902619845479812475 745 9847164999716251346903135 746 10280455722019708621802807 747 10732511768797158241556927 748 11204133071931723120504159 749 11696153128075591484969420 750 12209440384943561812788780 751 12744899683982355415546364 752 13303473761704594679233108 753 13886144811930809689146693 754 14493936111446007562403949 755 15127913711639192259205772 756 15789188198649856537692308 757 16478916524831979134975722 758 17198303914417046554525031 759 17948605846215038167788591 760 18731130116504331427471600 761 19547238985342809906645635 762 20398351409492379847235332 763 21285945365489006091411014 764 22211560266483398793663200 765 23176799476440745624006062 766 24183332925658292399197215 767 25232899831665808762640932 768 26327311529541553210690148 769 27468454416080134926623179 770 28658293012369820978255429 771 29898873149309859368062239 772 31192325281038697926153984 773 32540867931381962728367176 774 33946811278408828022849187 775 35412560882665708326608384 776 36940621564813170429397025 777 38533601438379972275795464 778 40194216103872232786176942 779 41925293010654097331397924 780 43729775993014228578556849 781 45610729987404539909521742 782 47571345938040039416853900 783 49614945898058540875713742 784 51744988334063684976848004 785 53965073642104275681116622 786 56278949883167000349171186 787 58690518746941955441645089 788 61203841752880457343244676 789 63823146697605425311432034 790 66552834358480217936555850 791 69397485463436152084072900 792 72361867937219404312358697 793 75450944435032971407260978 794 78669880174882246794071380 795 82024051080016224949849130 796 85519052243747469678921544 797 89160706729310136134302266 798 92955074717525550550641422 799 96908463016019571762426880 800 101027434944160686897091422 801 105318820608029051911182047 802 109789727580793203828521084 803 114447552004350404145435382 804 119299990128263726618317911 805 124355050303196349746963148 806 129621065446583881337979823 807 135106705998504075391490793 808 140820993386981440000895199 809 146773314022573142188658517 810 152973433842348723202697954 811 159431513424776052759510081 812 166158123697711661223738192 813 173164262262014272065919806 814 180461370354834156344564905 815 188061350477402670521963729 816 195976584712529498663483902 817 204219953758696149906402626 818 212804856708502331929090681 819 221745231599676359552552618 820 231055576768703735079721594 821 240750973038103938336679857 822 250847106768921396384701255 823 261360293812017769445861374 824 272307504392849248238002076 825 283706388965041151693564228 826 295575305070289392936270171 827 307933345243349894502355445 828 320800366001610961789662862 829 334197017961176791051416419 830 348144777122772693517087248 831 362665977371636123889188762 832 377783844238228472042087676 833 393522529968153647089573758 834 409907149950658555201514323 835 426963820558023225030850333 836 444719698449887880512317736 837 463203021397706827366043901 838 482443150687740039197582382 839 502470615162943419792164079 840 523317156965434878582612386 841 545015779044752102626237491 842 567600794499303113369146755 843 591107877819922983109781697 844 615574118108338971124080461 845 641038074345794018728810650 846 667539832788812196574376045 847 695121066573364503605364017 848 723825097611434036689764371 849 753696960865962823348792509 850 784783471094862850292100490 851 817133292157841300656741887 852 850797008982054499985358459 853 885827202287774396190417304 854 922278526178683479911441049 855 960207788703995082880058871 856 999674035505282622892114654 857 1040738636664740024260181554 858 1083465376874532613670085918 859 1127920549053154991679534808 860 1174173051539004308510622848 861 1222294488994714620007433669 862 1272359277162684593789758750 863 1324444751617027965961727343 864 1378631280660962852598692473 865 1435002382526236995335213820 866 1493644847036546102976034382 867 1554648861901193608684249978 868 1618108143813587324843075408 869 1684120074535155706147315697 870 1752785842150123404007874924 871 1824210587685778494708178435 872 1898503557299549465088527512 873 1975778260239701279843246889 874 2056152632796585756485763211 875 2139749208468844904984962232 876 2226695294575167727287580556 877 2317123155553356927923152065 878 2411170203196791207750040194 879 2508979194085366317668665055 880 2610698434480291072243433791 881 2716481992961407360779559670 882 2826489921093591123538784725 883 2940888482422339614236265508 884 3059850390109015355367417202 885 3183555053525101086729254886 886 3312188834139754384322791675 887 3445945311046508558571608480 888 3585025556484963815598687732 889 3729638421729777478800247579 890 3880000833732146719535415605 891 4036338102910218919020774953 892 4198884242503019591722386130 893 4367882299916847775903595309 894 4543584700505720319243279532 895 4726253604247467604241641865 896 4916161275793083478054128671 897 5113590468381115407152016512 898 5318834822130963145942712661 899 5532199277246777648215985886 900 5754000502679566955734268615 901 5984567340819474539427909370 902 6224241268810045181122497901 903 6473376877094140383700328081 904 6732342365828038427949037259 905 7001520059822355077082172693 906 7281306942688422183234012879 907 7572115210898411836459450389 908 7874372848492095484004276411 909 8188524223185530222075223839 910 8515030704669682551924849546 911 8854371305914379383385386203 912 9207043348318054895262225234 913 9573563151579868593111174957 914 9954466749201233937615487702 915 10350310630551856666390031143 916 10761672510475231921195932500 917 11189152127442437928057481436 918 11633372071294443155269731507 919 12094978641657128905208905095 920 12574642738150919381582460576 921 13073060783551985634527449613 922 13590955681110542669331800835 923 14129077807273668111361713633 924 14688206041099257334901507310 925 15269148831701328841955290613 926 15872745305113484424520927544 927 16499866412001089892148959564 928 17151416117711915247569474021 929 17828332636206757989012016329 930 18531589709460422289886728692 931 19262197933988757658372350031 932 20021206136215006968261924263 933 20809702798443219666923267136 934 21628817537278619117124950332 935 22479722636398749136036437321 936 23363634635640018458115502500 937 24281815978443909182802981188 938 25235576719778136856124181407 939 26226276296715830576569604290 940 27255325363943749282808451436 941 28324187696549427546060181715 942 29434382162512686997983256088 943 30587484767424066086646884460 944 31785130774040305915432599366 945 33029016899371193484516485776 946 34320903592099308004539333545 947 35662617393231452059752614949 948 37056053382974285000966903090 949 38503177716945107049166312673 950 40006030254936673290249233995 951 41566727285559278021453726597 952 43187464350214137014416821073 953 44870519169971875042909405056 954 46618254679046079718248084146 955 48433122168696316760924272771 956 50317664545527907753407882939 957 52274519708285009218952440985 958 54306424047393038261680501408 959 56416216071653934398990606758 960 58606840166641498932992135299 961 60881350489520205427602577795 962 63242915005174419460299266096 963 65694819668694813890247946642 964 68240472759463300891135815598 965 70883409372259173502729048453 966 73627296070986844939808150015 967 76475935710840408861890975149 968 79433272434921351095453421672 969 82503396851523223406679765796 970 85690551398534340830068348771 971 88999135901632517096557769410 972 92433713333165260185977845585 973 95999015778870852143305762781 974 99699950619842867943158771843 975 103541606937384392776042329825 976 107529262148687527525449138074 977 111668388881547657119876359062 978 115964662096592578518277255567 979 120423966465826087360537719812 980 125052404016589108351176365908 981 129856302050341891025474966008 982 134842221346023604093431723604 983 140016964658081893691951157341 984 145387585519598424240397751221 985 150961397361326002713522900194 986 156745982957825339240321086963 987 162749204212259506135226231370 988 168979212291834328554508730676 989 175444458126285448536375243855 990 182153703282223279906102800795 991 189116031226622043519036933005 992 196340858993195873770495492609 993 203837949265860250261039835125 994 211617422894001426963457056674 995 219689771854782303018047798007 996 228065872678218002461077215017 997 236757000351333418407875154064 998 245774842718274883076482243377 999 255131515393807780084541198455 1000 264839577208271123167407487873