1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 20 20 22 21 24 22 26 23 28 24 30 25 33 26 36 27 39 28 42 29 45 30 48 31 52 32 56 33 60 34 66 35 72 36 78 37 84 38 90 39 99 40 108 41 117 42 126 43 135 44 144 45 156 46 168 47 180 48 198 49 216 50 234 51 252 52 270 53 297 54 324 55 351 56 378 57 405 58 432 59 468 60 504 61 540 62 594 63 648 64 702 65 756 66 810 67 891 68 972 69 1053 70 1134 71 1215 72 1296 73 1404 74 1512 75 1620 76 1782 77 1944 78 2106 79 2268 80 2430 81 2673 82 2916 83 3159 84 3402 85 3645 86 3888 87 4212 88 4536 89 4860 90 5346 91 5832 92 6318 93 6804 94 7290 95 8019 96 8748 97 9477 98 10206 99 10935 100 11664 101 12636 102 13608 103 14580 104 16038 105 17496 106 18954 107 20412 108 21870 109 24057 110 26244 111 28431 112 30618 113 32805 114 34992 115 37908 116 40824 117 43740 118 48114 119 52488 120 56862 121 61236 122 65610 123 72171 124 78732 125 85293 126 91854 127 98415 128 104976 129 113724 130 122472 131 131220 132 144342 133 157464 134 170586 135 183708 136 196830 137 216513 138 236196 139 255879 140 275562 141 295245 142 314928 143 341172 144 367416 145 393660 146 433026 147 472392 148 511758 149 551124 150 590490 151 649539 152 708588 153 767637 154 826686 155 885735 156 944784 157 1023516 158 1102248 159 1180980 160 1299078 161 1417176 162 1535274 163 1653372 164 1771470 165 1948617 166 2125764 167 2302911 168 2480058 169 2657205 170 2834352 171 3070548 172 3306744 173 3542940 174 3897234 175 4251528 176 4605822 177 4960116 178 5314410 179 5845851 180 6377292 181 6908733 182 7440174 183 7971615 184 8503056 185 9211644 186 9920232 187 10628820 188 11691702 189 12754584 190 13817466 191 14880348 192 15943230 193 17537553 194 19131876 195 20726199 196 22320522 197 23914845 198 25509168 199 27634932 200 29760696 201 31886460 202 35075106 203 38263752 204 41452398 205 44641044 206 47829690 207 52612659 208 57395628 209 62178597 210 66961566 211 71744535 212 76527504 213 82904796 214 89282088 215 95659380 216 105225318 217 114791256 218 124357194 219 133923132 220 143489070 221 157837977 222 172186884 223 186535791 224 200884698 225 215233605 226 229582512 227 248714388 228 267846264 229 286978140 230 315675954 231 344373768 232 373071582 233 401769396 234 430467210 235 473513931 236 516560652 237 559607373 238 602654094 239 645700815 240 688747536 241 746143164 242 803538792 243 860934420 244 947027862 245 1033121304 246 1119214746 247 1205308188 248 1291401630 249 1420541793 250 1549681956 251 1678822119 252 1807962282 253 1937102445 254 2066242608 255 2238429492 256 2410616376 257 2582803260 258 2841083586 259 3099363912 260 3357644238 261 3615924564 262 3874204890 263 4261625379 264 4649045868 265 5036466357 266 5423886846 267 5811307335 268 6198727824 269 6715288476 270 7231849128 271 7748409780 272 8523250758 273 9298091736 274 10072932714 275 10847773692 276 11622614670 277 12784876137 278 13947137604 279 15109399071 280 16271660538 281 17433922005 282 18596183472 283 20145865428 284 21695547384 285 23245229340 286 25569752274 287 27894275208 288 30218798142 289 32543321076 290 34867844010 291 38354628411 292 41841412812 293 45328197213 294 48814981614 295 52301766015 296 55788550416 297 60437596284 298 65086642152 299 69735688020 300 76709256822 301 83682825624 302 90656394426 303 97629963228 304 104603532030 305 115063885233 306 125524238436 307 135984591639 308 146444944842 309 156905298045 310 167365651248 311 181312788852 312 195259926456 313 209207064060 314 230127770466 315 251048476872 316 271969183278 317 292889889684 318 313810596090 319 345191655699 320 376572715308 321 407953774917 322 439334834526 323 470715894135 324 502096953744 325 543938366556 326 585779779368 327 627621192180 328 690383311398 329 753145430616 330 815907549834 331 878669669052 332 941431788270 333 1035574967097 334 1129718145924 335 1223861324751 336 1318004503578 337 1412147682405 338 1506290861232 339 1631815099668 340 1757339338104 341 1882863576540 342 2071149934194 343 2259436291848 344 2447722649502 345 2636009007156 346 2824295364810 347 3106724901291 348 3389154437772 349 3671583974253 350 3954013510734 351 4236443047215 352 4518872583696 353 4895445299004 354 5272018014312 355 5648590729620 356 6213449802582 357 6778308875544 358 7343167948506 359 7908027021468 360 8472886094430 361 9320174703873 362 10167463313316 363 11014751922759 364 11862040532202 365 12709329141645 366 13556617751088 367 14686335897012 368 15816054042936 369 16945772188860 370 18640349407746 371 20334926626632 372 22029503845518 373 23724081064404 374 25418658283290 375 27960524111619 376 30502389939948 377 33044255768277 378 35586121596606 379 38127987424935 380 40669853253264 381 44059007691036 382 47448162128808 383 50837316566580 384 55921048223238 385 61004779879896 386 66088511536554 387 71172243193212 388 76255974849870 389 83881572334857 390 91507169819844 391 99132767304831 392 106758364789818 393 114383962274805 394 122009559759792 395 132177023073108 396 142344486386424 397 152511949699740 398 167763144669714 399 183014339639688 400 198265534609662 401 213516729579636 402 228767924549610 403 251644717004571 404 274521509459532 405 297398301914493 406 320275094369454 407 343151886824415 408 366028679279376 409 396531069219324 410 427033459159272 411 457535849099220 412 503289434009142 413 549043018919064 414 594796603828986 415 640550188738908 416 686303773648830 417 754934151013713 418 823564528378596 419 892194905743479 420 960825283108362 421 1029455660473245 422 1098086037838128 423 1189593207657972 424 1281100377477816 425 1372607547297660 426 1509868302027426 427 1647129056757192 428 1784389811486958 429 1921650566216724 430 2058911320946490 431 2264802453041139 432 2470693585135788 433 2676584717230437 434 2882475849325086 435 3088366981419735 436 3294258113514384 437 3568779622973916 438 3843301132433448 439 4117822641892980 440 4529604906082278 441 4941387170271576 442 5353169434460874 443 5764951698650172 444 6176733962839470 445 6794407359123417 446 7412080755407364 447 8029754151691311 448 8647427547975258 449 9265100944259205 450 9882774340543152 451 10706338868921748 452 11529903397300344 453 12353467925678940 454 13588814718246834 455 14824161510814728 456 16059508303382622 457 17294855095950516 458 18530201888518410 459 20383222077370251 460 22236242266222092 461 24089262455073933 462 25942282643925774 463 27795302832777615 464 29648323021629456 465 32119016606765244 466 34589710191901032 467 37060403777036820 468 40766444154740502 469 44472484532444184 470 48178524910147866 471 51884565287851548 472 55590605665555230 473 61149666232110753 474 66708726798666276 475 72267787365221799 476 77826847931777322 477 83385908498332845 478 88944969064888368 479 96357049820295732 480 103769130575703096 481 111181211331110460 482 122299332464221506 483 133417453597332552 484 144535574730443598 485 155653695863554644 486 166771816996665690 487 183448998696332259 488 200126180395998828 489 216803362095665397 490 233480543795331966 491 250157725494998535 492 266834907194665104 493 289071149460887196 494 311307391727109288 495 333543633993331380 496 366897997392664518 497 400252360791997656 498 433606724191330794 499 466961087590663932 500 500315450989997070 501 550346996088996777 502 600378541187996484 503 650410086286996191 504 700441631385995898 505 750473176484995605 506 800504721583995312 507 867213448382661588 508 933922175181327864 509 1000630901979994140 510 1100693992177993554 511 1200757082375992968 512 1300820172573992382 513 1400883262771991796 514 1500946352969991210 515 1651040988266990331 516 1801135623563989452 517 1951230258860988573 518 2101324894157987694 519 2251419529454986815 520 2401514164751985936 521 2601640345147984764 522 2801766525543983592 523 3001892705939982420 524 3302081976533980662 525 3602271247127978904 526 3902460517721977146 527 4202649788315975388 528 4502839058909973630 529 4953122964800970993 530 5403406870691968356 531 5853690776582965719 532 6303974682473963082 533 6754258588364960445 534 7204542494255957808 535 7804921035443954292 536 8405299576631950776 537 9005678117819947260 538 9906245929601941986 539 10806813741383936712 540 11707381553165931438 541 12607949364947926164 542 13508517176729920890 543 14859368894402912979 544 16210220612075905068 545 17561072329748897157 546 18911924047421889246 547 20262775765094881335 548 21613627482767873424 549 23414763106331862876 550 25215898729895852328 551 27017034353459841780 552 29718737788805825958 553 32420441224151810136 554 35122144659497794314 555 37823848094843778492 556 40525551530189762670 557 44578106683208738937 558 48630661836227715204 559 52683216989246691471 560 56735772142265667738 561 60788327295284644005 562 64840882448303620272 563 70244289318995588628 564 75647696189687556984 565 81051103060379525340 566 89156213366417477874 567 97261323672455430408 568 105366433978493382942 569 113471544284531335476 570 121576654590569288010 571 133734320049626216811 572 145891985508683145612 573 158049650967740074413 574 170207316426797003214 575 182364981885853932015 576 194522647344910860816 577 210732867956986765884 578 226943088569062670952 579 243153309181138576020 580 267468640099252433622 581 291783971017366291224 582 316099301935480148826 583 340414632853594006428 584 364729963771707864030 585 401202960148878650433 586 437675956526049436836 587 474148952903220223239 588 510621949280391009642 589 547094945657561796045 590 583567942034732582448 591 632198603870960297652 592 680829265707188012856 593 729459927543415728060 594 802405920297757300866 595 875351913052098873672 596 948297905806440446478 597 1021243898560782019284 598 1094189891315123592090 599 1203608880446635951299 600 1313027869578148310508 601 1422446858709660669717 602 1531865847841173028926 603 1641284836972685388135 604 1750703826104197747344 605 1896595811612880892956 606 2042487797121564038568 607 2188379782630247184180 608 2407217760893271902598 609 2626055739156296621016 610 2844893717419321339434 611 3063731695682346057852 612 3282569673945370776270 613 3610826641339907853897 614 3939083608734444931524 615 4267340576128982009151 616 4595597543523519086778 617 4923854510918056164405 618 5252111478312593242032 619 5689787434838642678868 620 6127463391364692115704 621 6565139347890741552540 622 7221653282679815707794 623 7878167217468889863048 624 8534681152257964018302 625 9191195087047038173556 626 9847709021836112328810 627 10832479924019723561691 628 11817250826203334794572 629 12802021728386946027453 630 13786792630570557260334 631 14771563532754168493215 632 15756334434937779726096 633 17069362304515928036604 634 18382390174094076347112 635 19695418043672224657620 636 21664959848039447123382 637 23634501652406669589144 638 25604043456773892054906 639 27573585261141114520668 640 29543127065508336986430 641 32497439772059170685073 642 35451752478610004383716 643 38406065185160838082359 644 41360377891711671781002 645 44314690598262505479645 646 47269003304813339178288 647 51208086913547784109812 648 55147170522282229041336 649 59086254131016673972860 650 64994879544118341370146 651 70903504957220008767432 652 76812130370321676164718 653 82720755783423343562004 654 88629381196525010959290 655 97492319316177512055219 656 106355257435830013151148 657 115218195555482514247077 658 124081133675135015343006 659 132944071794787516438935 660 141807009914440017534864 661 153624260740643352329436 662 165441511566846687124008 663 177258762393050021918580 664 194984638632355024110438 665 212710514871660026302296 666 230436391110965028494154 667 248162267350270030686012 668 265888143589575032877870 669 292476957948532536165657 670 319065772307490039453444 671 345654586666447542741231 672 372243401025405046029018 673 398832215384362549316805 674 425421029743320052604592 675 460872782221930056988308 676 496324534700540061372024 677 531776287179150065755740 678 584953915897065072331314 679 638131544614980078906888 680 691309173332895085482462 681 744486802050810092058036 682 797664430768725098633610 683 877430873845597608496971 684 957197316922470118360332 685 1036963759999342628223693 686 1116730203076215138087054 687 1196496646153087647950415 688 1276263089229960157813776 689 1382618346665790170964924 690 1488973604101620184116072 691 1595328861537450197267220 692 1754861747691195216993942 693 1914394633844940236720664 694 2073927519998685256447386 695 2233460406152430276174108 696 2392993292306175295900830 697 2632292621536792825490913 698 2871591950767410355080996 699 3110891279998027884671079 700 3350190609228645414261162 701 3589489938459262943851245 702 3828789267689880473441328 703 4147855039997370512894772 704 4466920812304860552348216 705 4785986584612350591801660 706 5264585243073585650981826 707 5743183901534820710161992 708 6221782559996055769342158 709 6700381218457290828522324 710 7178979876918525887702490 711 7896877864610378476472739 712 8614775852302231065242988 713 9332673839994083654013237 714 10050571827685936242783486 715 10768469815377788831553735 716 11486367803069641420323984 717 12443565119992111538684316 718 13400762436914581657044648 719 14357959753837051775404980 720 15793755729220756952945478 721 17229551704604462130485976 722 18665347679988167308026474 723 20101143655371872485566972 724 21536939630755577663107470 725 23690633593831135429418217 726 25844327556906693195728964 727 27998021519982250962039711 728 30151715483057808728350458 729 32305409446133366494661205 730 34459103409208924260971952 731 37330695359976334616052948 732 40202287310743744971133944 733 43073879261511155326214940 734 47381267187662270858836434 735 51688655113813386391457928 736 55996043039964501924079422 737 60303430966115617456700916 738 64610818892266732989322410 739 71071900781493406288254651 740 77532982670720079587186892 741 83994064559946752886119133 742 90455146449173426185051374 743 96916228338400099483983615 744 103377310227626772782915856 745 111992086079929003848158844 746 120606861932231234913401832 747 129221637784533465978644820 748 142143801562986812576509302 749 155065965341440159174373784 750 167988129119893505772238266 751 180910292898346852370102748 752 193832456676800198967967230 753 213215702344480218864763953 754 232598948012160238761560676 755 251982193679840258658357399 756 271365439347520278555154122 757 290748685015200298451950845 758 310131930682880318348747568 759 335976258239787011544476532 760 361820585796693704740205496 761 387664913353600397935934460 762 426431404688960437729527906 763 465197896024320477523121352 764 503964387359680517316714798 765 542730878695040557110308244 766 581497370030400596903901690 767 639647107033440656594291859 768 697796844036480716284682028 769 755946581039520775975072197 770 814096318042560835665462366 771 872246055045600895355852535 772 930395792048640955046242704 773 1007928774719361034633429596 774 1085461757390081114220616488 775 1162994740060801193807803380 776 1279294214066881313188583718 777 1395593688072961432569364056 778 1511893162079041551950144394 779 1628192636085121671330924732 780 1744492110091201790711705070 781 1918941321100321969782875577 782 2093390532109442148854046084 783 2267839743118562327925216591 784 2442288954127682506996387098 785 2616738165136802686067557605 786 2791187376145922865138728112 787 3023786324158083103900288788 788 3256385272170243342661849464 789 3488984220182403581423410140 790 3837882642200643939565751154 791 4186781064218884297708092168 792 4535679486237124655850433182 793 4884577908255365013992774196 794 5233476330273605372135115210 795 5756823963300965909348626731 796 6280171596328326446562138252 797 6803519229355686983775649773 798 7326866862383047520989161294 799 7850214495410408058202672815 800 8373562128437768595416184336 801 9071358972474249311700866364 802 9769155816510730027985548392 803 10466952660547210744270230420 804 11513647926601931818697253462 805 12560343192656652893124276504 806 13607038458711373967551299546 807 14653733724766095041978322588 808 15700428990820816116405345630 809 17270471889902897728045880193 810 18840514788984979339686414756 811 20410557688067060951326949319 812 21980600587149142562967483882 813 23550643486231224174608018445 814 25120686385313305786248553008 815 27214076917422747935102599092 816 29307467449532190083956645176 817 31400857981641632232810691260 818 34540943779805795456091760386 819 37681029577969958679372829512 820 40821115376134121902653898638 821 43961201174298285125934967764 822 47101286972462448349216036890 823 51811415669708693184137640579 824 56521544366954938019059244268 825 61231673064201182853980847957 826 65941801761447427688902451646 827 70651930458693672523824055335 828 75362059155939917358745659024 829 81642230752268243805307797276 830 87922402348596570251869935528 831 94202573944924896698432073780 832 103622831339417386368275281158 833 113043088733909876038118488536 834 122463346128402365707961695914 835 131883603522894855377804903292 836 141303860917387345047648110670 837 155434247009126079552412921737 838 169564633100864814057177732804 839 183695019192603548561942543871 840 197825405284342283066707354938 841 211955791376081017571472166005 842 226086177467819752076236977072 843 244926692256804731415923391828 844 263767207045789710755609806584 845 282607721834774690095296221340 846 310868494018252159104825843474 847 339129266201729628114355465608 848 367390038385207097123885087742 849 395650810568684566133414709876 850 423911582752162035142944332010 851 466302741027378238657238765211 852 508693899302594442171533198412 853 551085057577810645685827631613 854 593476215853026849200122064814 855 635867374128243052714416498015 856 678258532403459256228710931216 857 734780076770414194247770175484 858 791301621137369132266829419752 859 847823165504324070285888664020 860 932605482054756477314477530422 861 1017387798605188884343066396824 862 1102170115155621291371655263226 863 1186952431706053698400244129628 864 1271734748256486105428832996030 865 1398908223082134715971716295633 866 1526081697907783326514599595236 867 1653255172733431937057482894839 868 1780428647559080547600366194442 869 1907602122384729158143249494045 870 2034775597210377768686132793648 871 2204340230311242582743310526452 872 2373904863412107396800488259256 873 2543469496512972210857665992060 874 2797816446164269431943432591266 875 3052163395815566653029199190472 876 3306510345466863874114965789678 877 3560857295118161095200732388884 878 3815204244769458316286498988090 879 4196724669246404147915148886899 880 4578245093723349979543798785708 881 4959765518200295811172448684517 882 5341285942677241642801098583326 883 5722806367154187474429748482135 884 6104326791631133306058398380944 885 6613020690933727748229931579356 886 7121714590236322190401464777768 887 7630408489538916632572997976180 888 8393449338492808295830297773798 889 9156490187446699959087597571416 890 9919531036400591622344897369034 891 10682571885354483285602197166652 892 11445612734308374948859496964270 893 12590174007739212443745446660697 894 13734735281170049938631396357124 895 14879296554600887433517346053551 896 16023857828031724928403295749978 897 17168419101462562423289245446405 898 18312980374893399918175195142832 899 19839062072801183244689794738068 900 21365143770708966571204394333304 901 22891225468616749897718993928540 902 25180348015478424887490893321394 903 27469470562340099877262792714248 904 29758593109201774867034692107102 905 32047715656063449856806591499956 906 34336838202925124846578490892810 907 37770522023217637331236339982091 908 41204205843510149815894189071372 909 44637889663802662300552038160653 910 48071573484095174785209887249934 911 51505257304387687269867736339215 912 54938941124680199754525585428496 913 59517186218403549734069384214204 914 64095431312126899713613182999912 915 68673676405850249693156981785620 916 75541044046435274662472679964182 917 82408411687020299631788378142744 918 89275779327605324601104076321306 919 96143146968190349570419774499868 920 103010514608775374539735472678430 921 113311566069652911993709019946273 922 123612617530530449447682567214116 923 133913668991407986901656114481959 924 144214720452285524355629661749802 925 154515771913163061809603209017645 926 164816823374040599263576756285488 927 178551558655210649202208152642612 928 192286293936380699140839548999736 929 206021029217550749079470945356860 930 226623132139305823987418039892546 931 247225235061060898895365134428232 932 267827337982815973803312228963918 933 288429440904571048711259323499604 934 309031543826326123619206418035290 935 339934698208958735981127059838819 936 370837852591591348343047701642348 937 401741006974223960704968343445877 938 432644161356856573066888985249406 939 463547315739489185428809627052935 940 494450470122121797790730268856464 941 535654675965631947606624457927836 942 576858881809142097422518646999208 943 618063087652652247238412836070580 944 679869396417917471962254119677638 945 741675705183182696686095403284696 946 803482013948447921409936686891754 947 865288322713713146133777970498812 948 927094631478978370857619254105870 949 1019804094626876207943381179516457 950 1112513557774774045029143104927044 951 1205223020922671882114905030337631 952 1297932484070569719200666955748218 953 1390641947218467556286428881158805 954 1483351410366365393372190806569392 955 1606964027896895842819873373783508 956 1730576645427426292267555940997624 957 1854189262957956741715238508211740 958 2039608189253752415886762359032914 959 2225027115549548090058286209854088 960 2410446041845343764229810060675262 961 2595864968141139438401333911496436 962 2781283894436935112572857762317610 963 3059412283880628623830143538549371 964 3337540673324322135087429314781132 965 3615669062768015646344715091012893 966 3893797452211709157602000867244654 967 4171925841655402668859286643476415 968 4450054231099096180116572419708176 969 4820892083690687528459620121350524 970 5191729936282278876802667822992872 971 5562567788873870225145715524635220 972 6118824567761257247660287077098742 973 6675081346648644270174858629562264 974 7231338125536031292689430182025786 975 7787594904423418315204001734489308 976 8343851683310805337718573286952830 977 9178236851641885871490430615648113 978 10012622019972966405262287944343396 979 10847007188304046939034145273038679 980 11681392356635127472806002601733962 981 12515777524966208006577859930429245 982 13350162693297288540349717259124528 983 14462676251072062585378860364051572 984 15575189808846836630408003468978616 985 16687703366621610675437146573905660 986 18356473703283771742980861231296226 987 20025244039945932810524575888686792 988 21694014376608093878068290546077358 989 23362784713270254945612005203467924 990 25031555049932416013155719860858490 991 27534710554925657614471291846944339 992 30037866059918899215786863833030188 993 32541021564912140817102435819116037 994 35044177069905382418418007805201886 995 37547332574898624019733579791287735 996 40050488079891865621049151777373584 997 43388028753216187756136581092154716 998 46725569426540509891224010406935848 999 50063110099864832026311439721716980 1000 55069421109851315228942583693888678