4 4 5 0 6 5 7 5 8 15 9 16 10 30 11 36 12 60 13 75 14 116 15 149 16 217 17 273 18 386 19 491 20 664 21 839 22 1116 23 1399 24 1829 25 2292 26 2937 27 3656 28 4638 29 5729 30 7187 31 8840 32 10984 33 13430 34 16558 35 20138 36 24657 37 29846 38 36288 39 43736 40 52880 41 63430 42 76289 43 91159 44 109106 45 129841 46 154724 47 183452 48 217727 49 257270 50 304125 51 358195 52 421967 53 495398 54 581654 55 680881 56 796916 57 930247 58 1085592 59 1263810 60 1470784 61 1707889 62 1982321 63 2296328 64 2658728 65 3072651 66 3549155 67 4092681 68 4716678 69 5427447 70 6241546 71 7167449 72 8225682 73 9427522 74 10798143 75 12352672 76 14122063 77 16125941 78 18402604 79 20977595 80 23897713 81 27196197 82 30930485 83 35143053 84 39904627 85 45269233 86 51323430 87 58136157 88 65813291 89 74441615 90 84151076 91 95050822 92 107299372 93 121033802 94 136447677 95 153711861 96 173062884 97 194713178 98 218950682 99 246039497 100 276329871 101 310148044 102 347920545 103 390049644 104 437052871 105 489425713 106 547795909 107 612771210 108 685112850 109 765564748 110 855047781 111 954471813 112 1064949777 113 1187590369 114 1323738447 115 1474742923 116 1642225191 117 1827824377 118 2033493592 119 2261219478 120 2513353144 121 2792298375 122 3100880490 123 3442004920 124 3819063188 125 4235558761 126 4695560450 127 5203287044 128 5763611545 129 6381608148 130 7063107418 131 7814201063 132 8641859676 133 9553386230 134 10557102658 135 11661754717 136 12877267330 137 14214096527 138 15684069390 139 17299671436 140 19074977846 141 21024881194 142 23166116049 143 25516420608 144 28095673900 145 30924978276 146 34027920707 147 37429580556 148 41157916666 149 45242695771 150 49717031099 151 54616214766 152 59979421277 153 65848451805 154 72269609180 155 79292346420 156 86971344698 157 95365049010 158 104537969796 159 114559114522 160 125504520746 161 137455579032 162 150501839805 163 164739206457 164 180273042749 165 197216250159 166 215692691877 167 235835148744 168 257789112248 169 281710599579 170 307770354725 171 336151540669 172 367054370026 173 400693674169 174 437304036238 175 477137214501 176 520467829253 177 567590669552 178 618826970798 179 674521608950 180 735050059532 181 800815463683 182 872256343977 183 949843580516 184 1034088936886 185 1125541963332 186 1224799458440 187 1332502287020 188 1449345878354 189 1576077021866 190 1713505484667 191 1862500816707 192 2024005250789 193 2199030523274 194 2388672203752 195 2594106618596 196 2816606729764 197 3057539224378 198 3318382168156 199 3600722289367 200 3906274606801 201 4236880044941 202 4594527217977 203 4981350478691 204 5399654160387 205 5851911133915 206 6340789796445 207 6869153333220 208 7440089713100 209 8056911831865 210 8723190932333 211 9442757766664 212 10219739841219 213 11058563896911 214 11963997367613 215 12941152449104 216 13995532340961 217 15133037152577 218 16360015500582 219 17683272688953 220 19110128216980 221 20648426664369 222 22306601905249 223 24093691099849 224 26019406417544 225 28094152785138 226 30329107933480 227 32736244550489 228 35328419747064 229 38119402266792 230 41123972514422 231 44357955768521 232 47838333936132 233 51583285755152 234 55612311815153 235 59946282747948 236 64607579122581 237 69620149016958 238 75009664471300 239 80803589901172 240 87031357247214 241 93724446763917 242 100916583150403 243 108643830728478 244 116944812958381 245 125860824171506 246 135436075476840 247 145717825334572 248 156756655069500 249 168606621218279 250 181325564092836 251 194975285060290 252 209621892352047 253 225336006676821 254 242193148834368 255 260273977872332 256 279664725395740 257 300457470873351 258 322750628537650 259 346649264816065 260 372265644229317 261 399719595014454 262 429139120981860 263 460660821966075 264 494430579886636 265 530604041276964 266 569347386593262 267 610837883478264 268 655264749154290 269 702829783978297 270 753748338480367 271 808250037661364 272 866579865369852 273 928998991696959 274 995785988603042 275 1067237774044255 276 1143670975006413 277 1225423003379058 278 1312853584228583 279 1406345980939141 280 1506308708286768 281 1613176926270826 282 1727414360589503 283 1849514886562366 284 1980004681962675 285 2119444025829132 286 2268429711154550 287 2427597086076678 288 2597622757934020 289 2779226907248011 290 2973176318048328 291 3180286999577426 292 3401427581371431 293 3637522281504019 294 3889554710357745 295 4158571228348548 296 4445685207046683 297 4752080825482971 298 5079017842413618 299 5427835885750847 300 5799959797037460 301 6196904474468556 302 6620280857331942 303 7071801391348138 304 7553286728009545 305 8066671888672419 306 8614013763602644 307 9197498059546911 308 9819447692554047 309 10482330615014543 310 11188769206441734 311 11941549086665845 312 12743629622034123 313 13598153843141878 314 14508460196860552 315 15478093702171617 316 16510819092442747 317 17610633357890552 318 18781780440556242 319 20028765328159243 320 21356370482049716 321 22769671667885636 322 24274056316364605 323 25875241296778068 324 27579293434647187 325 29392649456823533 326 31322138914819563 327 33375006558062991 328 35558937938583502 329 37882084497583404 330 40353092160141722 331 42981129451413660 332 45775919423814820 333 48747771157122274 334 51907615397697660 335 55267039835900983 336 58838328881452232 337 62634503154557362 338 66669363867914324 339 70957537019273697 340 75514522901355720 341 80356745537304257 342 85501607900128037 343 90967547191345558 344 96774096414848645 345 102941946168603094 346 109493013287363990 347 116450509890585458 348 123839019889811612 349 131684576116531720 350 140014745576412289 351 148858715574744939 352 158247388694355558 353 168213478936255405 354 178791617508072800 355 190018460107201739 356 201932804723789831 357 214575711320634287 358 227990632983613662 359 242223549388257338 360 257323112778661652 361 273340796759887580 362 290331058745426939 363 308351505785609554 364 327463075298289278 365 347730219827457035 366 369221108071460340 367 392007830668148536 368 416166623749842571 369 441778098081817763 370 468927487609608204 371 497704904526237441 372 528205615545718636 373 560530325747922061 374 594785485602349106 375 631083606749207513 376 669543603116357538 377 710291142130703580 378 753459023631615137 379 799187570375461869 380 847625048839405733 381 898928103297839760 382 953262223039993167 383 1010802224748414502 384 1071732771136844714 385 1136248906857322796 386 1204556634089879391 387 1276873507762119072 388 1353429274199242196 389 1434466532046438529 390 1520241440734557879 391 1611024454162076509 392 1707101106435734351 393 1808772826114792391 394 1916357807459872836 395 2030191913854847611 396 2150629643661398412 397 2278045132327195261 398 2412833222886238672 399 2555410577258365431 400 2706216862470835466 401 2865715982741488465 402 3034397393650711197 403 3212777467794958315 404 3401400950397185521 405 3600842472646733132 406 3811708163619509853 407 4034637326871595898 408 4270304225077305592 409 4519419937038382035 410 4782734333127147108 411 5061038131643041466 412 5355165084991726339 413 5665994256255123574 414 5994452438082128457 415 6341516672462157558 416 6708216926537803009 417 7095638880925366114 418 7504926889113372690 419 7937287062246383231 420 8393990541488804777 421 8876376910012767425 422 9385857810676330914 423 9923920719079841398 424 10492132942166341742 425 11092145789627435964 426 11725698992635132431 427 12394625314626972530 428 13100855433317230289 429 13846423036031176684 430 14633470212464849770 431 15464253084266766045 432 16341147760783470858 433 17266656557554562380 434 18243414572497344272 435 19274196553458749117 436 20361924158012070001 437 21509673536202288428 438 22720683343431457854 439 23998363111104443507 440 25346302088974873278 441 26768278483635514144 442 28268269214255671528 443 29850460106777219735 444 31519256655294311842 445 33279295268493308283 446 35135455138027179287 447 37092870643283612519 448 39156944438078826878 449 41333361130280679293 450 43628101709112343686 451 46047458627596911515 452 48598051704754745260 453 51286844751409417796 454 54121163094699064828 455 57108711901534466255 456 60257595487274660734 457 63576337506186796260 458 67073902221916892422 459 70759716750835681802 460 74643694489211651059 461 78736259613407841589 462 83048372877626034445 463 87591558594710136326 464 92377933039061190111 465 97420234153515827177 466 102731852814718948837 467 108326865535281958014 468 114220068873778749655 469 120427015427359617098 470 126964051695730522897 471 133848357687868218120 472 141097988579089317711 473 148731918286627726498 474 156770085291496812885 475 165233440571719402196 476 174143997996305302599 477 183524887042200987380 478 193400408206651325627 479 203796090974663655953 480 214738754738669023556 481 226256572527818876129 482 238379137970448773082 483 251137535345263412504 484 264564413173022347018 485 278694061202902726317 486 293562491275544519296 487 309207521916048910850 488 325668867171366036238 489 342988229545021310263 490 361209397578301249036 491 380378347931279543330 492 400543352549949880609 493 421755090774013285981 494 444066767011464647541 495 467534233836570592423 496 492216121180074423182 497 518173971471352957646 498 545472381447117713536 499 574179150490609189441 500 604365436265029948619 501 636105917510665046632 502 669478964822102827596 503 704566819282040556556 504 741455779824583729192 505 780236399213131304366 506 821003689566480632534 507 863857337328659565465 508 908901928681244094326 509 956247185306218798565 510 1006008211568049991580 511 1058305753037790532592 512 1113266467503075825478 513 1171023208404108954443 514 1231715321920198240708 515 1295488957667148311975 516 1362497394316769446191 517 1432901380122072411994 518 1506869489752711908036 519 1584578497450965642040 520 1666213768013033045138 521 1751969665636627283844 522 1842049982247387757973 523 1936668385379956801342 524 2036048887342252123162 525 2140426335778336923179 526 2250046927483122188948 527 2365168745629191999066 528 2486062322393138752966 529 2613011227192244944888 530 2746312682663407845931 531 2886278208651992333806 532 3033234296497961891308 533 3187523113950936313175 534 3349503243168860014069 535 3519550452203472455800 536 3698058502607603128516 537 3885439993647437475643 538 4082127245948893604346 539 4288573225150643959366 540 4505252508601992529326 541 4732662295777616551010 542 4971323465672797020442 543 5221781681961772611979 544 5484608549425619125597 545 5760402822555357463414 546 6049791670098303284400 547 6353431996589766712491 548 6672011824920287607478 549 7006251741131623754778 550 7356906405795741276348 551 7724766133337466070284 552 8110658543982847801035 553 8515450289878882374573 554 8940048860420330876678 555 9385404468533558487246 556 9852512023334434905604 557 10342413191135850524139 558 10856198550633126174442 559 11395009844491473445042 560 11960042333607628815605 561 12552547256543627769531 562 13173834400883535481701 563 13825274789312719643031 564 14508303487686937545390 565 15224422538222401935701 566 15975204025631650231298 567 16762293279700768414084 568 17587412222734334458190 569 18452362865764124705013 570 19359030962597135331661 571 20309389826038382443063 572 21305504316065036425343 573 22349535004769338762342 574 23443742528603388029240 575 24590492133271956996539 576 25792258422623093187843 577 27051630317461802094886 578 28371316236518572560916 579 29754149506132231612606 580 31203094011830998115590 581 32721250099065731892125 582 34311860737307250240687 583 35978317955521337206874 584 37724169564343732700025 585 39553126173799366430415 586 41469068523087033398646 587 43476055132182082608892 588 45578330293073008395288 589 47780332411376705779197 590 50086702717546911066917 591 52502294359504143068054 592 55032181897412000481836 593 57681671213611464152298 594 60456309860069259378411 595 63361897857643046739951 596 66404498971281782612777 597 69590452476872425606016 598 72926385445754578607744 599 76419225564150559687588 600 80076214515588232038679 601 83904921945238606185027 602 87913260036466575904572 603 92109498720341563448957 604 96502281550805313139944 605 101100642268232025436610 606 105914022086669285371659 607 110952287729660225688394 608 116225750252734974175168 609 121745184679829159490170 610 127521850494741420020600 611 133567513017454020897340 612 139894465709694940154049 613 146515553442357695869136 614 153444196772686310724146 615 160694417266878976743045 616 168280863919829639240211 617 176218840710964803574459 618 184524335352012282189718 619 193214049269250825404893 620 202305428880525717892249 621 211816698213483204877274 622 221766892930113557722795 623 232175895808298700648692 624 243064473750644055786695 625 254454316375900000880923 626 266368076268859116597382 627 278829410949041273426088 628 291863026640108135606288 629 305494723905756788127510 630 319751445240574437058090 631 334661324687507147516818 632 350253739577489446241057 633 366559364469295420163135 634 383610227392788134070090 635 401439768480582604140430 636 420082901099539561440934 637 439576075574650617026128 638 459957345625632382182522 639 481266437616975174827508 640 503544822751375267894525 641 526835792316174443012769 642 551184536123115083651635 643 576638224260661221018765 644 603246092310402888549536 645 631059530157230880617985 646 660132174556902619529965 647 690520005602000086907558 648 722281447262969288485974 649 755477472157503194507101 650 790171710739069335465830 651 826430565071129431413801 652 864323327393087826376714 653 903922303658910272060286 654 945302942270898464908600 655 988543968205152925905342 656 1033727522768968282030020 657 1080939309203578591162290 658 1130268744391667056231510 659 1181809116901342508234126 660 1235657751646690541491597 661 1291916181416397065118945 662 1350690325572890171309671 663 1412090676194925974971556 664 1476232491990174286252883 665 1543236000273922597550468 666 1613226607366475769947459 667 1686335117730467127562520 668 1762697962228742917849682 669 1842457435851190249517415 670 1925761945321477798467246 671 2012766266961456767494225 672 2103631815256896037773722 673 2198526922534074440970115 674 2297627130226195218098057 675 2401115492173510434557563 676 2509182890474197980925546 677 2622028364367040597146129 678 2739859452704031605496180 679 2862892550534134832660707 680 2991353280400646062846973 681 3125476878916817347020621 682 3265508599270004844809545 683 3411704130265950451738068 684 3564330032615034148705738 685 3723664193122846336692756 686 3889996297542550773224012 687 4063628322806215783458227 688 4244875049452587978527952 689 4434064595027727836133680 690 4631538969340694562013785 691 4837654652414698593340275 692 5052783196085699044621202 693 5277311850157994684068868 694 5511644214144042488553610 695 5756200915572718008573899 696 6011420315974398648062972 697 6277759245607715182735498 698 6555693768123847333467370 699 6845719976320271880709948 700 7148354820274168239588558 701 7464136969101389299802492 702 7793627707732893469555860 703 8137411870056018120391194 704 8496098809922112723122993 705 8870323411477439227753674 706 9260747140437018314883622 707 9668059137876539517682772 708 10092977358289368935383478 709 10536249753611335843177436 710 10998655505097590208408308 711 11481006304891853567246987 712 11984147689320272296111445 713 12508960425898696854145145 714 13056361956244988852140761 715 13627307897045375277143982 716 14222793601438201223131491 717 14843855783136893416368615 718 15491574205840532211033158 719 16167073440440207602745532 720 16871524692768915895067956 721 17606147704604145371067154 722 18372212730885673709592988 723 19171042596074430560057001 724 20004014832846290273318278 725 20872563906280295329062517 726 21778183526984355821015251 727 22722429056569807513267467 728 23706920009186251399625291 729 24733342652799569582794503 730 25803452714213567558571336 731 26919078191810783270744648 732 28082122280324156458119999 733 29294566411930484292191894 734 30558473418312503016691364 735 31875990818320380412939741 736 33249354236240310850511274 737 34680890955667195457241475 738 36173023614377600695967228 739 37728274045594509928265865 740 39349267271458303606054770 741 41038735654520499871930000 742 42799523213524911161050896 743 44634590109750565193718337 744 46547017310665653107702673 745 48540011437659945207870704 746 50616909805126523061207439 747 52781185658191303084139016 748 55036453616922537886602061 749 57386475334890616387121156 750 59835165380514423224240702 751 62386597349680305461596216 752 65045010218719927568102759 753 67814814946895975660103990 754 70700601338181393159868724 755 73707145172194760962779295 756 76839415614829981884106010 757 80102582919211076954995081 758 83502026428319779282254034 759 87043342890753561975075465 760 90732355101832611360596274 761 94575120882403243215372818 762 98577942408492970507737894 763 102747375905122321943353228 764 107090241718436101046468443 765 111613634780489590114298959 766 116324935481935912288572507 767 121231820968058704022278532 768 126342276874561529728133094 769 131664609519750905478009136 770 137207458570777348104959838 771 142979810201854357827331449 772 148991010763467000747285688 773 155250780981870090262606038 774 161769230709336133038867132 775 168556874245937377559200398 776 175624646254879377739887951 777 182983918293766731021666101 778 190646515985492425540389348 779 198624736852848063196846740 780 206931368842345813294956774 781 215579709563195148053010990 782 224583586268859287514279776 783 233957376609118915811913102 784 243716030182146730605833064 785 253875090916653873240616879 786 264450720315845636009404678 787 275459721595540928327539694 788 286919564750593348568729194 789 298848412584433507775199822 790 311265147738449739935796326 791 324189400758676380453374444 792 337641579239277990819816404 793 351642898083146152220320863 794 366215410922074476141280172 795 381382042739888327141150435 796 397166623744193267426876074 797 413593924533406602916991474 798 430689692608171657150564234 799 448480690277351730841781986 800 466994734011393579188187566 801 486260735297052533318892948 802 506308743050232449327030201 803 527169987645009561679760807 804 548876926619849825137382579 805 571463292123468100078141146 806 594964140165909554364802637 807 619415901742005277969836062 808 644856435897690503428436222 809 671325084811389055927779522 810 698862730966222170260450557 811 727511856490670200380047592 812 757316604749103079892282604 813 788322844265633348746849860 814 820578235068781402554957069 815 854132297546661515762612817 816 889036483906698292028339529 817 925344252336297379423367814 818 963111143965478576841597230 819 1002394862735104344995711804 820 1043255358279223342702452454 821 1085754911932900789213748759 822 1129958225982116808940056682 823 1175932516275411190256145462 824 1223747608322506951151079126 825 1273476037008506585446818131 826 1325193150058176760629044839 827 1378977215388483479276756434 828 1434909532493854464634017114 829 1493074548012598579469173048 830 1553559975629646338755014732 831 1616456920475059090447306245 832 1681860008184936644083246521 833 1749867518795992533556848941 834 1820581525652726644061306003 835 1894108039511147498202510538 836 1970557158031167875171976261 837 2050043220855232404575132054 838 2132684970479452684302913042 839 2218605719129404255235153790 840 2307933521862039253719367538 841 2400801356121524833760482361 842 2497347307986739141157356609 843 2597714765355026482123951821 844 2702052618317399523426054069 845 2810515466987798567316759360 846 2923263837060313819976547357 847 3040464403376292654441183638 848 3162290221795307728848139246 849 3288920969672616289772510365 850 3420543195258604406792017922 851 3557350576345050498621473671 852 3699544188496770560030315917 853 3847332783217285418370940834 854 4000933076411801908642325591 855 4160570047521669893759632451 856 4326477249720114991395923455 857 4498897131570767808132714873 858 4678081370567201923043590334 859 4864291218984327655055386781 860 5057797862490305352975180504 861 5258882791981258015319371832 862 5467838189120081626193053778 863 5684967326075321212120523278 864 5910584979976382888594955782 865 6145017862617152710143849696 866 6388605065961766518428644332 867 6641698524023289300556487792 868 6904663491709200412463638808 869 7177879041245897881721576491 870 7461738576819136982240251819 871 7756650368087032682894739843 872 8063038103248628192505296216 873 8381341462372245477243977355 874 8712016711715990593934466626 875 9055537319795608501223323134 876 9412394595984944730285818246 877 9783098352458817824296877726 878 10168177590320204636278832561 879 10568181210780036520487531381 880 10983678752292176560263056924 881 11415261154574526859649608242 882 11863541550483808793714502421 883 12329156086742063763747879453 884 12812764774551995549925487898 885 13315052371171058563149690454 886 13836729293555918093362602688 887 14378532565224133947632131787 888 14941226797524468873021587849 889 15525605206545065424926276949 890 16132490666936305354688045321 891 16762736803965811856429333390 892 17417229125173850991204542060 893 18096886193041038980838061480 894 18802660840134502597219130336 895 19535541428245508302640314434 896 20296553153089494744738777882 897 21086759396189758443711418879 898 21907263125627889463779843108 899 22759208347398060563499393789 900 23643781609168314678696413496 901 24562213558309955284554289878 902 25515780556126664389638975029 903 26505806350277165140483410496 904 27533663807460548617583836662 905 28600776708500108063992630594 906 29708621608041932739467665579 907 30858729761156088107636398774 908 32052689119214070206950795740 909 33292146397492988771251161279 910 34578809217048616035583020045 911 35914448323481761957031632704 912 37300899885320333973708146445 913 38740067874827710133443140268 914 40233926534152587179346708653 915 41784522929830099297720021465 916 43393979598755619830747980858 917 45064497288854100869092696060 918 46798357797786984592328542272 919 48597926913147446751326200089 920 50465657457721984682008879146 921 52404092443512880493396804296 922 54415868338351939923544567956 923 56503718449060759863581500234 924 58670476425257846484644146423 925 60919079888046672035188347534 926 63252574187973646603654784931 927 65674116296788279610500744721 928 68186978837703174889385475336 929 70794554259004994855171887360 930 73500359156044084925717553126 931 76308038746794839732807040780 932 79221371506367387816707683167 933 82244273966027213897175576467 934 85380805682480575496823872576 935 88635174383372069506030537235 936 92011741295155540973887304821 937 95515026659701340285969382529 938 99149715446232284240234124904 939 102920663265396722016576832527 940 106832902492531943376953672694 941 110891648607402421991459431244 942 115102306757958749171145516280 943 119470478555910623176345719542 944 124001969112186255916003848672 945 128702794320615437501983439713 946 133579188398471311710740808879 947 138637611692789352258916147234 948 143884758761699918328289657242 949 149327566740314031995701428800 950 154973224001041328351959431768 951 160829179118543574849084489500 952 166903150149889316681329036396 953 173203134240822277290832833250 954 179737417569442682763286714976 955 186514585638971919221891485735 956 193543533931683479833213917702 957 200833478936480210884380220582 958 208393969563038157627876046406 959 216234898955861930295142321630 960 224366516722066396083579529449 961 232799441587153560672266467208 962 241544674493554955072457971128 963 250613612157195335131773404352 964 260018061097868622699214117203 965 269770252159736071384601840711 966 279882855538827671971567387548 967 290368996334982698851585328068 968 301242270646274630083997404444 969 312516762224558812941364584711 970 324207059711431422770375080794 971 336328274474522236460979606073 972 348896059064737475327538012934 973 361926626315746531978705011198 974 375436769107746577924621782959 975 389443880818263128874261508412 976 403965976483534356152787375421 977 419021714694800661582873300327 978 434630420254663556448987807859 979 450812107619504597485421633651 980 467587505154853965610129711871 981 484978080231481523432890381909 982 503006065190942056316782624357 983 521694484210249979103361708488 984 541067181096381665381485405731 985 561148848042311498850533155832 986 581965055377378856804498637292 987 603542282345859847562248377827 988 625907948948781475517281753247 989 649090448885165775187742069699 990 673119183630132848353136420531 991 698024597688519749627831687112 992 723838215063996211960367937650 993 750592676984969566371581096013 994 778321780929983355189191826007 995 807060520996714401817681652024 996 836845129660179143453977508802 997 867713120967255110243841505024 998 899703335216229553172775104336 999 932855985171683412104647573666 1000 967212703866731587735962631518