1 1 2 1 3 2 4 3 5 4 6 6 7 9 8 13 9 17 10 24 11 32 12 42 13 56 14 73 15 96 16 123 17 158 18 201 19 254 20 320 21 402 22 504 23 624 24 774 25 955 26 1172 27 1436 28 1755 29 2138 30 2592 31 3140 32 3789 33 4560 34 5478 35 6564 36 7851 37 9362 38 11146 39 13240 40 15696 41 18574 42 21942 43 25880 44 30456 45 35796 46 42000 47 49196 48 57546 49 67217 50 78403 51 91308 52 106212 53 123374 54 143124 55 165840 56 191925 57 221860 58 256146 59 295414 60 340320 61 391628 62 450204 63 517017 64 593163 65 679816 66 778416 67 890468 68 1017698 69 1162080 70 1325784 71 1511248 72 1721157 73 1958642 74 2227050 75 2530214 76 2872422 77 3258400 78 3693480 79 4183496 80 4735120 81 5355629 82 6053190 83 6836902 84 7716858 85 8704296 86 9811552 87 11052612 88 12442728 89 13998906 90 15740088 91 17687160 92 19863280 93 22293976 94 25007796 95 28035968 96 31413222 97 35177966 98 39372497 99 44043648 100 49242873 101 55027332 102 61459716 103 68609300 104 76552460 105 85373280 106 95164398 107 106027476 108 118075020 109 131430194 110 146228640 111 162619636 112 180766995 113 200850718 114 223068204 115 247636800 116 274794246 117 304801768 118 337945890 119 374540430 120 414929568 121 459489853 122 508634528 123 562815276 124 622526820 125 688310568 126 760758609 127 840518528 128 928297629 129 1024870240 130 1131081168 131 1247853614 132 1376196048 133 1517208942 134 1672093444 135 1842159552 136 2028837534 137 2233685522 138 2458403040 139 2704842530 140 2975021888 141 3271139784 142 3595589664 143 3950979184 144 4340145219 145 4766175672 146 5232430242 147 5742562978 148 6300547662 149 6910703206 150 7577726514 151 8306719112 152 9103224234 153 9973263390 154 10923374520 155 11960655904 156 13092811032 157 14328202232 158 15675899064 159 17145740892 160 18748398384 161 20495439856 162 22399406229 163 24473886896 164 26733609762 165 29194526592 166 31873915842 167 34790487996 168 37964499126 169 41417875251 170 45174342320 171 49259576398 172 53701348560 173 58529696640 174 63777103308 175 69478685331 176 75672402200 177 82399275732 178 89703636186 179 97633368908 180 106240199040 181 115579986320 182 125713041972 183 136704475504 184 148624558224 185 161549129176 186 175560009096 187 190745465568 188 207200702156 189 225028383612 190 244339203744 191 265252487416 192 287896855530 193 312410907638 194 338943983382 195 367656966720 196 398723144307 197 432329135238 198 468675878904 199 507979712540 200 550473493207 201 596407835848 202 646052419800 203 699697388586 204 757654860828 205 820260532488 206 887875420700 207 960887691120 208 1039714652148 209 1124804871024 210 1216640439072 211 1315739403812 212 1422658358218 213 1537995245184 214 1662392302788 215 1796539267280 216 1941176776212 217 2097100001124 218 2265162548474 219 2446280614276 220 2641437459264 221 2851688133408 222 3078164588892 223 3322081108664 224 3584740106869 225 3867538346123 226 4171973551062 227 4499651521902 228 4852293660852 229 5231745076712 230 5639983205376 231 6079127013456 232 6551446837626 233 7059374863274 234 7605516367572 235 8192661621600 236 8823798681838 237 9502126997680 238 10231071916566 239 11014300184792 240 11855736451680 241 12759580929422 242 13730328121309 243 14772786899990 244 15892101851736 245 17093776028612 246 18383695233540 247 19768153854184 248 21253882477372 249 22848077189844 250 24558430912560 251 26393166723042 252 28361073349827 253 30471543002112 254 32734611615792 255 35161001811648 256 37762168471035 257 40550347414546 258 43538607153120 259 46740903954978 260 50172140503072 261 53848228270170 262 57786153994842 263 62004050236272 264 66521270624688 265 71358469809720 266 76537688499802 267 82082443967412 268 88017826219980 269 94370600410176 270 101169315518400 271 108444420101264 272 116228385243346 273 124555835252088 274 133463686615266 275 142991295612928 276 153180615353376 277 164076362363294 278 175726193851606 279 188180895916900 280 201494583450576 281 215724912554986 282 230933306071512 283 247185193265990 284 264550264059584 285 283102739289216 286 302921657480064 287 324091179291134 288 346700910793029 289 370846246478707 290 396628733558672 291 424156458226444 292 453544455886470 293 484915146275276 294 518398795119846 295 554134003987104 296 592268229805618 297 632958336216672 298 676371177904086 299 722684220737792 300 772086199216734 301 824777813555928 302 880972468929112 303 940897059074400 304 1004792797288326 305 1072916096813864 306 1145539504510422 307 1222952690129342 308 1305463494712504 309 1393399041720088 310 1487106914167296 311 1586956402208296 312 1693339824296232 313 1806673927300382 314 1927401369332852 315 2055992290331124 316 2192945975589960 317 2338792617284270 318 2494095180272532 319 2659451376984096 320 2835495759091920 321 3022901931643656 322 3222384896907408 323 3434703535634452 324 3660663233148591 325 3901118659211192 326 4156976709165336 327 4429199617150036 328 4718808249883806 329 5026885591699596 330 5354580431927040 331 5703111265477880 332 6073770419651310 333 6467928418378642 334 6887038599098196 335 7332641995159696 336 7806372499115418 337 8309962322883350 338 8845247770916635 339 9414175344953100 340 10018808196986688 341 10661332952218592 342 11344066920991866 343 12069465721785625 344 12840131338598352 345 13658820636167424 346 14528454359552460 347 15452126642930104 348 16433115058384788 349 17474891232534992 350 18581132063059227 351 19755731568636304 352 21002813406270120 353 22326744094267602 354 23732146977200700 355 25223916976478112 356 26807236167500238 357 28487590229358348 358 30270785815161276 359 32162968892474408 360 34170644108472912 361 36300695232658785 362 38560406739456940 363 40957486590083642 364 43500090279474948 365 46196846217616616 366 49056882516482640 367 52089855260427512 368 55305978337051888 369 58716054916885710 370 62331510667632720 371 66164428797511006 372 70227587026770360 373 74534496589561478 374 79099443377565328 375 83937531336366528 376 89064728239780116 377 94497913966032928 378 100254931410576564 379 106354640176831952 380 112816973191684128 381 119662996404086368 382 126914971726090632 383 134596423394291164 384 142732207929166278 385 151348587884096592 386 160473309585845438 387 170135685075923896 388 180366678477581490 389 191198997017039938 390 202667186950713984 391 214807734651831840 392 227659173129552541 393 241262194267061700 394 255659767076574198 395 270897262290447296 396 287022583614243000 397 304086305997353408 398 322141821282747860 399 341245491622728900 400 361456811066548737 401 382838575743529494 402 405457063092958872 403 429382220603732368 404 454687864566296448 405 481451889349899876 406 509756487752075682 407 539688382995061920 408 571339072968639492 409 604805087356136198 410 640188258300545136 411 677596005318356100 412 717141635186957700 413 758944657578219046 414 803131117248728976 415 849833943632893824 416 899193318736745644 417 951357064260410908 418 1006481048943828048 419 1064729617161219610 420 1126276039851660384 421 1191302988926211614 422 1260003036344508388 423 1332579179122449036 424 1409245391578235670 425 1490227206213597642 426 1575762324673396224 427 1666101260310593964 428 1761508013959363820 429 1862260784591959104 430 1968652716628579104 431 2080992685738629656 432 2199606125089365324 433 2324835894067883366 434 2457043191617860220 435 2596608516436407360 436 2743932676379323806 437 2899437849552389792 438 3063568699665329292 439 3236793548382210632 440 3419605607507294720 441 3612524274000482977 442 3816096490961244504 443 4030898177866436716 444 4257535733522024580 445 4496647615331387688 446 4748905998695679528 447 5015018520512542188 448 5295730110950866467 449 5591824917882323058 450 5904128328553168731 451 6233509093318351776 452 6580881556465814226 453 6947207999442838960 454 7333501102013095866 455 7740826527163617480 456 8170305635859643308 457 8623118338027977614 458 9100506086477901108 459 9603775020757458792 460 10134299268325909248 461 10693524410734314184 462 11282971122899882544 463 11904238993944885104 464 12559010538466426070 465 13249055407549200384 466 13976234809239554250 467 14742506148719434726 468 15549927898855144836 469 16400664712332826500 470 17296992787126819584 471 18241305497591483896 472 19236119304076102434 473 20284079954533748640 474 21387968992295492112 475 22550710584793515290 476 23775378688752426738 477 25065204568099682766 478 26423584681597874136 479 27854088958036570116 480 29360469477612734112 481 30946669579077180448 482 32616833413082365462 483 34375315963165816416 484 36226693556808338775 485 38175774890045459752 486 40227612590245435458 487 42387515342763931040 488 44661060608474278840 489 47054107960358947408 490 49572813068708796312 491 52223642365858268236 492 55013388422807892252 493 57949186071632225964 494 61038529309090263896 495 64289289018596576784 496 67709731549352435556 497 71308538193293242320 498 75094825602393654204 499 79078167190822419428 500 83268615568549760832 501 87676726055095096776 502 92313581324461455126 503 97190817234568831824 504 102320649897018394797 505 107715904045593551496 506 113390042764576825984 507 119357198640826265046 508 125632206406415710896 509 132230637141842413072 510 139168834112910624960 511 146463950317822257282 512 154133987824520202669 513 162197838981971044216 514 170675329592965037874 515 179587264139931460736 516 188955473159589743136 517 198802862866507825824 518 209153467130288924986 519 220032501915882652776 520 231466422301475125632 521 243482982193698084046 522 256111296865239573474 523 269381908445783291342 524 283326854503014666518 525 297979739856724445526 526 313375811775525694272 527 329552038712447574168 528 346547192742821412048 529 364401935875148291161 530 383158910413541220944 531 402862833558239808582 532 423560596439211080982 533 445301367786651474688 534 468136702451350034076 535 492120654997548959280 536 517309898600827203316 537 543763849494190886904 538 571544797216294034508 539 600718040927230986528 540 631352032069245545280 541 663518523662086143470 542 697292726535818418480 543 732753472817302281064 544 769983387000909905886 545 809069064948630252536 546 850101261180239831784 547 893175084830305780184 548 938390204665539111814 549 985851063573653960476 550 1035667102953011315112 551 1087952997451687647484 552 1142828900524306467552 553 1200420701295907469832 554 1260860293243842928350 555 1324285855231285409088 556 1390842145449692937018 557 1460680808852060813550 558 1533960698684819616444 559 1610848212752833980688 560 1691517645080148347152 561 1776151553658363268320 562 1864941145004966772522 563 1958086676285925755810 564 2055797875789827131880 565 2158294382575828506120 566 2265806206153532414834 567 2378574207090773947605 568 2496850599484634252928 569 2620899476271952754270 570 2750997358398557873472 571 2887433768910816059840 572 3030511833080035019616 573 3180548905718472367440 574 3337877226896536744182 575 3502844607323590099920 576 3675815144709750885843 577 3857169972483711559490 578 4047308042301211326707 579 4246646941841683044124 580 4455623749455341371584 581 4674695927291132243542 582 4904342254606771377828 583 5145063803035836240576 584 5397384955664074682970 585 5661854471847033840936 586 5939046599785262826000 587 6229562238960167077210 588 6534030154624791106122 589 6853108246638608895592 590 7187484875034143809376 591 7537880244806491414188 592 7905047852523847684062 593 8289775997469637936234 594 8692889360143033758624 595 9115250651066542427496 596 9557762332976118826274 597 10021368419601231932104 598 10507056354380252120256 599 11015858972599623848520 600 11548856550595422178866 601 12107178945811171558682 602 12692007831668535425376 603 13304579031376692300196 604 13946184954982399412712 605 14618177144146784032692 606 15321968929325880140448 607 16059038204232069893312 608 16830930322660817700938 609 17639261122983971573604 610 18485720085836480462544 611 19372073630758260616752 612 20300168557798102766418 613 21271935640341049556402 614 22289393375687161416298 615 23354651900185670024640 616 24469917076017234913704 617 25637494757017349114494 618 26859795241246571460936 619 28139337918339439963190 620 29478756120002715699776 621 30880802182387906075968 622 32348352729430335970632 623 33884414186630891825418 624 35492128535155803567000 625 37174779316545411751057 626 38935797898756293720406 627 40778770014711353615904 628 42707442585002964706116 629 44725730836882308470204 630 46837725732177650500728 631 49047701717314349072288 632 51360124809161115329272 633 53779661031002143282696 634 56311185213532272181662 635 58959790176396353026784 636 61730796306441483379980 637 64629761549526468841528 638 67662491833435711921072 639 70835051940176120954256 640 74153776846697774997936 641 77625283553871108603222 642 81256483424379868360536 643 85054595051046997997426 644 89027157678005433068144 645 93182045198056420996992 646 97527480750526337114844 647 102072051944941740034844 648 106824726736890721333953 649 111794869983531959170032 650 116992260707348117670172 651 122427110097923638207128 652 128110080282757700145336 653 134052303899403613159426 654 140265404502559309455228 655 146761517841119384558592 656 153553314041643782103378 657 160654020736198347628498 658 168077447174085633376596 659 175838009358609924385240 660 183950756251711398842112 661 192431397091064714560844 662 201296329866066909043584 663 210562671001045832025936 664 220248286296000180477666 665 230371823177244479952256 666 240952744312476661723770 667 252011362647016136752224 668 263568877920281535157644 669 275647414723989642250768 670 288270062166069647812320 671 301460915206896580977104 672 315245117737165085743254 673 329648907469549832167658 674 344699662719236860579518 675 360425951151467138036372 676 376857580577410503762369 677 394025651882995911373616 678 411962614178759522540388 679 430702322262348306440286 680 450280096489034492840800 681 470732785149461698565124 682 492098829457864678505568 683 514418331258183354350444 684 537733123559840935407222 685 562086844019473435632936 686 587525011489598710858137 687 614095105760099324838712 688 641846650623473280900720 689 670831300400089826354064 690 701102930065177154308608 691 732717729124980702270542 692 765734299395463698142508 693 800213756843093405541504 694 836219837653670978594016 695 873819008701830447965056 696 913080582600765319325388 697 954076837518944627788740 698 996883141958073243963932 699 1041578084694333720250644 700 1088243610093040752159489 701 1136965159015250342273154 702 1187831815543607174349360 703 1240936459763801239567180 704 1296375926847445931452184 705 1354251172692007723181568 706 1414667446383614400062994 707 1477734469759171048844324 708 1543566624355229079678756 709 1612283146042500748974146 710 1684008327656809850464576 711 1758871729949628940761352 712 1837008401194203271432530 713 1918559105796606619357376 714 2003670562274946295991844 715 2092495690984346359868832 716 2185193871980311658841556 717 2281931213428635652421616 718 2382880830986177186818104 719 2488223138593630708940436 720 2598146151138859495080720 721 2712845799467491740546228 722 2832526258236312478091289 723 2957400287124548411357836 724 3087689585938469871310380 725 3223625164165845207935838 726 3365447725558721070610350 727 3513408068345781614236484 728 3667767501699209177660524 729 3828798279105552368369477 730 3996784049315641391464176 731 4172020325575115614425904 732 4354814973864672923587248 733 4545488720907768239296124 734 4744375682733201279983752 735 4951823914610900719051872 736 5168195983211266414176144 737 5393869561871720510125440 738 5629238049888693328913718 739 5874711216789169613900336 740 6130715872573211872241088 741 6397696564957591115740208 742 6676116304690865414042334 743 6966457320051998048555096 744 7269221841687959702454408 745 7584932918990779144195128 746 7914135269261245856286966 747 8257396160955009079987638 748 8615306332357204941678288 749 8988480947084068980853876 750 9377560587864314710676160 751 9783212290109457524517368 752 10206130616840821670698444 753 10647038776601754133351836 754 11106689786046687641854728 755 11585867678964206785212224 756 12085388763559290857070060 757 12606102929890513897245170 758 13148895009431276252498952 759 13714686188800229898349824 760 14304435479785032283726176 761 14919141247865551784076550 762 15559842801527734637627616 763 16227622044747672477989826 764 16923605195117085978897016 765 17648964570176591155925832 766 18404920444621877967852708 767 19192742981150425096326888 768 20013754237822764409395978 769 20869330254922705925827286 770 21760903224415519683553952 771 22689963745221981623103204 772 23658063167649590792600298 773 24666816030450330427608652 774 25717902594107230893205536 775 26813071474089905844986060 776 27954142377962324365864910 777 29143008950374577413751700 778 30381641730124476647778426 779 31672091223634698402214932 780 33016491099357078646709376 781 34417061507787779555780160 782 35876112531955646957907808 783 37396047773431358695623096 784 38979368079097212463983723 785 40628675414116852705142344 786 42346676886751158910938252 787 44136188930881198536258710 788 46000141652321851156144002 789 47941583345240766767342784 790 49963685185236992722801152 791 52069746105882250923843854 792 54263197865785773667040040 793 56547610313511158962549192 794 58926696857951249845588876 795 61404320152054919228780352 796 63984497998098271008014796 797 66671409483002493811020256 798 69469401352521879705896076 799 72382994633458741724297736 800 75416891513407574150836183 801 78575982487889263860718170 802 81865353785107923302281758 803 85290295078948506232179968 804 88856307501233234667708456 805 92569111964669584431505728 806 96434657808352658389059920 807 100459131778130786445473640 808 104648967354605725175715600 809 109010854442018460491548094 810 113551749431769014397406104 811 118278885654834406844654030 812 123199784237883752943013046 813 128322265378444042672472416 814 133654460055045178969934832 815 139204822188869100479714288 816 144982141274046024059971548 817 150995555494381860432448096 818 157254565344965443164107150 819 163769047777793285219683752 820 170549270891263987879590336 821 177605909184135099028105230 822 184950059395303119099531660 823 192593256951563432299564280 824 200547493046332277157305308 825 208825232373168444084103536 826 217439431538819363447132850 827 226403558181435717297661668 828 235731610820551850685187440 829 245438139466417309095433340 830 255538267017289005304697632 831 266047711474355188496134588 832 276982809005062816877682036 833 288360537886760598027505790 834 300198543363752257740997908 835 312515163452080034437042944 836 325329455727628544918338992 837 338661225134455588360432336 838 352531052851620883824343854 839 366960326258197801781287684 840 381971270037618719878139808 841 397586978464023501785327695 842 413831448914854685254529278 843 430729616655574271694628692 844 448307390944067533318471212 845 466591692504051195372139644 846 485610492418618800895447572 847 505392852496937392409028645 848 525968967169059144457155418 849 547370206965831696113621620 850 569629163642984210450002674 851 592779697010635183358030560 852 616856983531715524448759808 853 641897566755129120602395160 854 667939409651885968831180448 855 695021948924942960060661120 856 723186151366077620866808340 857 752474572335803814714945350 858 782931416445118826947290432 859 814602600520751944608751394 860 847535818938569026274206144 861 881780611412879436968935308 862 917388433332594841123949688 863 954412728738507659438647016 864 992909006039394616156371540 865 1032934916568211889898519624 866 1074550336083337414910296990 867 1117817449323637244333872358 868 1162800837730091396422200708 869 1209567570450815027653369024 870 1258187298750558139363292736 871 1308732353950166551963835104 872 1361277849026043869190109858 873 1415901784004374278072163054 874 1472685155289754884921836064 875 1531712069072949967777063272 876 1593069858967724099884103124 877 1656849208032142951854985610 878 1723144275335356342711442760 879 1792052827236704517011652624 880 1863676373550022864982910336 881 1938120308772269505828880090 882 2015494058562072030949417497 883 2095911231660491974041952172 884 2179489777453246340408791640 885 2266352149380813193225064832 886 2356625474410291423006570476 887 2450441728790592516868985908 888 2547937920320523467103709788 889 2649256277367584671526463360 890 2754544444883864588504267760 891 2863955687674274285668651968 892 2977649101181540517762008088 893 3095789830061876457849520376 894 3218549294835086195047607748 895 3346105426903044133825816080 896 3478642912241035823680092357 897 3616353444077364956288982912 898 3759435984887935303188400914 899 3908097038044219723018710856 900 4062550929465144829905040881 901 4223020099635964039454053860 902 4389735406370178137977388560 903 4562936438704006845471493728 904 4742871842326832843721656814 905 4929799656965447891977618920 906 5123987666154846023809389648 907 5325713759843748885326902196 908 5535266310299031433183882870 909 5752944561789761025009962580 910 5979059034548689106769578064 911 6213931943526762219720779136 912 6457897632474568750263096564 913 6711303023903631319825469616 914 6974508085500114084778535382 915 7247886313583862720027281472 916 7531825234226756018673493092 917 7826726922666146729867797022 918 8133008541671730769693591224 919 8451102899547534620002232312 920 8781459028474877861424573184 921 9124542783927179353277044708 922 9480837465913360907734842564 923 9850844462833391182082922912 924 10235083918757236317339572304 925 10634095424967174570490855622 926 11048438736633123098749413744 927 11478694515521350605955982068 928 11925465099668745128975759418 929 12389375300987708833165376126 930 12871073231800798942526974848 931 13371231161339465442425487454 932 13890546403277692372143876638 933 14429742235409072370404499216 934 14989568852614877126077924002 935 15570804354311074193585740320 936 16174255767604029913173212844 937 16800760107427876490049023570 938 17451185474981258535351388196 939 18126432195827461562882413132 940 18827433999069815051121606336 941 19555159239063810545480213068 942 20310612161178637257651643752 943 21094834213173872513697512736 944 21908905403811932239983127502 945 22753945710383650310698305984 946 23631116536883079356213317824 947 24541622224628356329551444008 948 25486711617188322829468875888 949 26467679681539603960378948432 950 27485869187446104413737643262 951 28542672447122452179774353916 952 29639533117314887979475284750 953 30777948066007543239119228410 954 31959469306039055320321962462 955 33185705997994122766778641344 956 34458326524816995082987127688 957 35779060640679114194065909920 958 37149701696721273641683062684 959 38572108946381836314842909858 960 40048209933116854214685932640 961 41580002963415470279962989585 962 43169559668114862134512753000 963 44819027655123323484387663444 964 46530633256767987983740020210 965 48306684375095302809247715912 966 50149573428567780113741152224 967 52061780403719922486574208144 968 54045876015459666692388986105 969 56104524979829355957246062232 970 58240489403172276734616789168 971 60456632291787328513154899254 972 62755921186295585912008716750 973 65141431925088518356123800498 974 67616352541378615637247544064 975 70183987298529295006762599208 976 72847760868502410126274564200 977 75611222658428622485112837450 978 78478051290478516791453254832 979 81452059240390833298229105856 980 84537197640198749580115535168 981 87737561250885974984357640946 982 91057393610901733057924682796 983 94501092366667717979679840980 984 98073214791421044309509415684 985 101778483498955297458621373752 986 105621792359047273781166632172 987 109608212621590121988419404296 988 113742999256694616661678218792 989 118031597518269473854415611008 990 122479649738849230789683463200 991 127093002363704537545770632192 992 131877713232545039735677658748 993 136840059117409666998476385952 994 141986543525633393559092785440 995 147323904777083724096267102656 996 152859124365174611647209171876 997 158599435611490576240929085052 998 164552332624189815948093202052 999 170725579570702451312054821720 1000 177127220275599095327559788640