1 0 2 0 3 1 4 1 5 1 6 2 7 1 8 2 9 2 10 3 11 3 12 5 13 4 14 5 15 7 16 8 17 7 18 10 19 10 20 14 21 14 22 15 23 17 24 23 25 23 26 27 27 30 28 36 29 36 30 46 31 48 32 56 33 61 34 68 35 76 36 90 37 91 38 105 39 116 40 134 41 140 42 159 43 172 44 196 45 214 46 235 47 254 48 292 49 306 50 345 51 376 52 418 53 446 54 500 55 541 56 601 57 643 58 710 59 766 60 860 61 910 62 999 63 1088 64 1194 65 1282 66 1409 67 1510 68 1665 69 1783 70 1951 71 2096 72 2300 73 2455 74 2674 75 2893 76 3146 77 3357 78 3664 79 3926 80 4284 81 4581 82 4954 83 5321 84 5786 85 6181 86 6681 87 7170 88 7758 89 8280 90 8966 91 9585 92 10348 93 11064 94 11909 95 12756 96 13763 97 14655 98 15777 99 16874 100 18164 101 19350 102 20796 103 22199 104 23847 105 25441 106 27258 107 29071 108 31219 109 33209 110 35593 111 37950 112 40619 113 43223 114 46255 115 49267 116 52685 117 56028 118 59847 119 63681 120 68094 121 72305 122 77143 123 82076 124 87546 125 92988 126 99137 127 105285 128 112240 129 119131 130 126860 131 134668 132 143407 133 152065 134 161754 135 171703 136 182574 137 193471 138 205692 139 218024 140 231734 141 245473 142 260585 143 276118 144 293194 145 310371 146 329260 147 348650 148 369822 149 391235 150 414877 151 438903 152 465168 153 491940 154 521029 155 551046 156 583642 157 616660 158 652772 159 689940 160 730181 161 771147 162 815722 163 861560 164 911123 165 961963 166 1016699 167 1073212 168 1134349 169 1196681 170 1264206 171 1333854 172 1408591 173 1485420 174 1568213 175 1653683 176 1745355 177 1839620 178 1940838 179 2045499 180 2157918 181 2273103 182 2396749 183 2524960 184 2661713 185 2802815 186 2953757 187 3109790 188 3276635 189 3448663 190 3632356 191 3822554 192 4025442 193 4234655 194 4457796 195 4689491 196 4935449 197 5189617 198 5460635 199 5741204 200 6039764 201 6348236 202 6675850 203 7016102 204 7377254 205 7750668 206 8146975 207 8558493 208 8994501 209 9445731 210 9924739 211 10421188 212 10947003 213 11491967 214 12068447 215 12667602 216 13301096 217 13956849 218 14651064 219 15372160 220 16133804 221 16922912 222 17757106 223 18623411 224 19537751 225 20486409 226 21486752 227 22526343 228 23623236 229 24759880 230 25959391 231 27205572 232 28517814 233 29879726 234 31314889 235 32806052 236 34375472 237 36004266 238 37718737 239 39500538 240 41375732 241 43320247 242 45366196 243 47493501 244 49728248 245 52048762 246 54487735 247 57021772 248 59684306 249 62448333 250 65351410 251 68368327 252 71535581 253 74823301 254 78274434 255 81862709 256 85624695 257 89531138 258 93630280 259 97889061 260 102355039 261 106991811 262 111851647 263 116903731 264 122197136 265 127693257 266 133451243 267 139436059 268 145702488 269 152209537 270 159025185 271 166105413 272 173516266 273 181213350 274 189266901 275 197637483 276 206393241 277 215483549 278 224994182 279 234876621 280 245208891 281 255936860 282 267154415 283 278808569 284 290988171 285 303636992 286 316852136 287 330582234 288 344927128 289 359818452 290 375375964 291 391536528 292 408408886 293 425928447 294 444221402 295 463221698 296 483052173 297 503640829 298 525128052 299 547444659 300 570731294 301 594900399 302 620116615 303 646306123 304 673616299 305 701967667 306 731533724 307 762231495 308 794238244 309 827459218 310 862090868 311 898045866 312 935519098 313 974408705 314 1014936241 315 1057012861 316 1100843188 317 1146328877 318 1193717592 319 1242902195 320 1294130798 321 1347285975 322 1402638769 323 1460091402 324 1519908278 325 1581968516 326 1646576101 327 1713624122 328 1783407331 329 1855801187 330 1931150153 331 2009324892 332 2090668235 333 2175050027 334 2262837546 335 2353919666 336 2448662181 337 2546922369 338 2649130508 339 2755155146 340 2865409832 341 2979747943 342 3098643577 343 3221959634 344 3350162090 345 3483106053 346 3621297767 347 3764613233 348 3913573914 349 4068009499 350 4228516524 351 4394947579 352 4567876512 353 4747154752 354 4933425725 355 5126546096 356 5327159675 357 5535109922 358 5751112991 359 5975030616 360 6207591020 361 6448609244 362 6698905775 363 6958346050 364 7227715578 365 7506869874 366 7796694981 367 8097050631 368 8408848304 369 8731922236 370 9067268203 371 9414756575 372 9775396109 373 10149026100 374 10536763020 375 10938499920 376 11355326768 377 11787121021 378 12235128848 379 12699224390 380 13180677697 381 13679347287 382 14196608505 383 14732396936 384 15288095607 385 15863592568 386 16460425632 387 17078547249 388 17719500239 389 18383207113 390 19071397457 391 19784011526 392 20522808231 393 21287746863 394 22080710604 395 22901744508 396 23752766154 397 24633761140 398 25546884652 399 26492191574 400 27471836809 401 28485863758 402 29536660801 403 30624341962 404 31751323870 405 32917733710 406 34126175756 407 35376883443 408 36672558138 409 38013350629 410 39402250060 411 40839525351 412 42328170874 413 43868498338 414 45463784601 415 47114421302 416 48823759407 417 50592208910 418 52423421981 419 54317930583 420 56279501235 421 58308606188 422 60409376005 423 62582498662 424 64832108132 425 67158937413 426 69567519120 427 72058693381 428 74637165528 429 77303790622 430 80063646123 431 82917788870 432 85871450185 433 88925701014 434 92086220833 435 95354341636 436 98735811741 437 102232030216 438 105849336571 439 109589260851 440 113458357561 441 117458239489 442 121595943348 443 125873435634 444 130297946195 445 134871461757 446 139601842721 447 144491416634 448 149548253985 449 154774766562 450 160179761737 451 165765897873 452 171542277593 453 177511790187 454 183684147065 455 190062679933 456 196657436468 457 203471807897 458 210516767503 459 217796135418 460 225321166647 461 233095889405 462 241132508940 463 249435519666 464 258017513716 465 266883287674 466 276046310670 467 285511968822 468 295294329465 469 305398879752 470 315840857212 471 326626407894 472 337771184524 473 349281786258 474 361175071569 475 373458250939 476 386148816933 477 399254418239 478 412793856930 479 426775546041 480 441219075924 481 456133159144 482 471538910629 483 487446094712 484 503876405492 485 520840220927 486 538360913302 487 556449711304 488 575131049200 489 594416760606 490 614332972031 491 634892669089 492 656123070528 493 678037841127 494 700666160772 495 724023070050 496 748138723072 497 773029048292 498 798726604282 499 825248470912 500 852628630073 501 880885179355 502 910054349752 503 940156027653 504 971227921227 505 1003290889937 506 1036385365552 507 1070534076054 508 1105779094587 509 1142144389563 510 1179675145249 511 1218397099504 512 1258357414592 513 1299583549733 514 1342125620799 515 1386013463370 516 1431299418394 517 1478014780064 518 1526215761945 519 1575936157739 520 1627234445672 521 1680146391738 522 1734734586641 523 1791037562402 524 1849120607765 525 1909024630529 526 1970819064858 527 2034548067992 528 2100284480322 529 2168074563658 530 2237996220474 531 2310099342432 532 2384465039682 533 2461146363245 534 2540229818957 535 2621772221256 536 2705864053911 537 2792565505259 538 2881972982967 539 2974151064276 540 3069200782928 541 3167190049390 542 3268226631820 543 3372383803853 544 3479773792241 545 3590474248367 546 3704604836848 547 3822248441192 548 3943530663799 549 4068539092648 550 4197407188743 551 4330228843443 552 4467143918555 553 4608251576680 554 4753700585307 555 4903597343767 556 5058097190641 557 5217312708358 558 5381409641452 559 5550507755702 560 5724780889546 561 5904355773835 562 6089416822795 563 6280099933567 564 6476598278826 565 6679055158975 566 6887675995238 567 7102614006947 568 7324084361151 569 7552248885996 570 7787336533379 571 8029519464973 572 8279037813394 573 8536074115334 574 8800882650679 575 9073658381117 576 9354668073953 577 9644117208025 578 9942289590392 579 10249404188221 580 10565758217814 581 10891583149487 582 11227194666695 583 11572839214551 584 11928847780605 585 12295481139917 586 12673089808807 587 13061951595837 588 13462434943349 589 13874832393248 590 14299535073273 591 14736854494115 592 15187200391910 593 15650902514617 594 16128395238673 595 16620028782122 596 17126259111647 597 17647456409835 598 18184103816599 599 18736594709040 600 19305436658700 601 19891044307415 602 20493955690264 603 21114612300342 604 21753577768585 605 22411318724791 606 23088432474273 607 23785413837492 608 24502890722699 609 25241385516037 610 26001562561577 611 26783976626086 612 27589325568605 613 28418194885522 614 29271323201257 615 30149332469624 616 31052997304008 617 31982974498587 618 32940084987981 619 33925024126925 620 34938654522434 621 35981710420296 622 37055103587062 623 38159613672398 624 39296198138531 625 40465679072695 626 41669069505652 627 42907241302572 628 44181258211729 629 45492040030126 630 46840712465595 631 48228249023940 632 49655832408890 633 51124491096386 634 52635473875098 635 54189870848593 636 55788994131348 637 57433992597707 638 59126254464854 639 60866996241633 640 62657675328809 641 64499575202391 642 66394236541176 643 68343017795237 644 70347537187055 645 72409228387726 646 74529799709330 647 76710768778442 648 78953931847910 649 81260887363457 650 83633533489807 651 86073561814581 652 88582965098566 653 91163528576793 654 93817356631156 655 96546336411543 656 99352679063361 657 102238374880609 658 105205758178687 659 108256933131895 660 111394353269061 661 114620235096856 662 117937169080497 663 121347500226544 664 124853947690444 665 128458984190785 666 132165480101104 667 135976046943247 668 139893702249243 669 143921198236387 670 148061717728567 671 152318168932958 672 156693896554321 673 161191964884798 674 165815902155727 675 170568946429166 676 175454802482187 677 180476882714211 678 185639097215578 679 190945046627217 680 196398840052476 681 202004271565498 682 207765672540485 683 213687050909793 684 219772957007663 685 226027611296036 686 232455812041476 687 239062014998310 688 245851260652937 689 252828241665288 690 259998273280982 691 267366305193924 692 274937922009986 693 282718339292385 694 290713439744663 695 298928727497613 696 307370383261460 697 316044200526709 698 324956695387953 699 334113978848648 700 343522894196107 701 353189876130196 702 363122136156539 703 373326459921970 704 383810422232766 705 394581168591304 706 405646675876465 707 417014479161285 708 428692960895604 709 440690048440164 710 453014572634177 711 465674891440585 712 478680277660625 713 492039531249806 714 505762417368375 715 519858208914382 716 534337163185193 717 549209039996946 718 564484639214380 719 580174244949326 720 596289202406977 721 612840329411116 722 629839571068169 723 647298329039770 724 665229143424773 725 683644012034587 726 702556136094319 727 721978150607485 728 741923923157657 729 762406745296982 730 783441209626263 731 805041315713706 732 827222389243527 733 849999155083259 734 873387739804217 735 897403651784352 736 922063820857665 737 947384558914573 738 973383683665887 739 1000078362902528 740 1027487307812757 741 1055628573627025 742 1084521840411089 743 1114186118934485 744 1144642071945202 745 1175909685938504 746 1208010695990959 747 1240966139589677 748 1274798835280434 749 1309530900150466 750 1345186335812404 751 1381788411452073 752 1419362325948008 753 1457932546677043 754 1497525564464986 755 1538167125492288 756 1579885040361744 757 1622706366427261 758 1666660349700878 759 1711775453652258 760 1758082373851197 761 1805611026446140 762 1854393683075250 763 1904461809159519 764 1955849276518063 765 2008589155341154 766 2062717043352395 767 2118267720858268 768 2175278556418748 769 2233786087058787 770 2293829590248635 771 2355447486772206 772 2418680991571866 773 2483570477638539 774 2550159255417842 775 2618489766608938 776 2688607462702979 777 2760556932242113 778 2834385930872749 779 2910141328486197 780 2987873241168832 781 3067630894007799 782 3149466940363518 783 3233433126348224 784 3319584688483748 785 3407975978969911 786 3498665023711241 787 3591708934254354 788 3687168598062588 789 3785103991255644 790 3885579060340184 791 3988656826846246 792 4094404380370851 793 4202887895445338 794 4314177827754839 795 4428343706260193 796 4545459432162935 797 4665598008943645 798 4788837047973210 799 4915253224653919 800 5044927953851551 801 5177941734011907 802 5314380037919525 803 5454327424582462 804 5597873542700656 805 5745107148564452 806 5896122359064685 807 6051012388790076 808 6209875944513180 809 6372810862041343 810 6539920760185218 811 6711308361543611 812 6887082334500515 813 7067350496644691 814 7252226889172153 815 7441824717376982 816 7636263570849617 817 7835662234355345 818 8040146223040500 819 8249840234474481 820 8464875869256708 821 8685383970090068 822 8911502634798911 823 9143369201047674 824 9381128456496381 825 9624924497090748 826 9874909224795921 827 10131233875295905 828 10394057713061776 829 10663539373650258 830 10939845948482864 831 11223143913250577 832 11513608417207990 833 11811414095718220 834 12116744676853770 835 12429783391905533 836 12750722829197653 837 13079755171908902 838 13417082418228545 839 13762906193767574 840 14117438227510277 841 14480889953972974 842 14853483429706572 843 15235440471075432 844 15626993782579636 845 16028375971653717 846 16439831067612385 847 16861603039041530 848 17293947634413043 849 17737120655068908 850 18191390252031653 851 18657024708124257 852 19134305018406343 853 19623512448241280 854 20124941596473369 855 20638887426473354 856 21165658599430881 857 21705564329143816 858 22258928209418185 859 22826074440716238 860 23407342063701937 861 24003070908353015 862 24613616343151943 863 25239334674091780 864 25880598191221369 865 26537780323010587 866 27211271270142573 867 27901462510068744 868 28608762789182932 869 29333582366677065 870 30076349618849498 871 30837494559327965 872 31617465897246887 873 32416714260306700 874 33235709816821834 875 34074924874695951 876 34934851879192094 877 35815985687295660 878 36718842296705061 879 37643940303055340 880 38591820087480366 881 39563024977714438 882 40558121128602092 883 41577677869995861 884 42622288073226104 885 43692548173273558 886 44789079224801867 887 45912506151697569 888 47063479295457709 889 48242653219498460 890 49450709152886585 891 50688332853825415 892 51956237565609796 893 53255141566146620 894 54585791884787946 895 55948940928543762 896 57345370799901331 897 58775869494190316 898 60241256081348442 899 61742355927320978 900 63280026500629717 901 64855132087144445 902 66468570612016002 903 68121247296714888 904 69814102026885646 905 71548082667205218 906 73324173355909114 907 75143366690911704 908 77006692790492193 909 78915190896440575 910 80869939497548537 911 82872026808735907 912 84922581594981079 913 87022743101933446 914 89173693002054576 915 91376624124294823 916 93632773082651208 917 95943388543481334 918 98309765008513549 919 100733209677332000 920 103215077184129195 921 105756735796434013 922 108359603358040031 923 111025112224891275 924 113754745960841730 925 116550003667510944 926 119412438034151404 927 122343618203982090 928 125345168704676756 929 128418731669981654 930 131566007184364096 931 134788713889659153 932 138088630403647703 933 141467555205762572 934 144927349388495241 935 148469895109576735 936 152097139278222736 937 155811051226490314 938 159613668062078790 939 163507050525190481 940 167493329447273476 941 171574660873240340 942 175753274127065474 943 180031425116979456 944 184411445570303103 945 188895695540314253 946 193486614255473583 947 198186670874935273 948 202998416533108803 949 207924434059314820 950 212967392045020184 951 218129992479099938 952 223415026062082104 953 228825319047405865 954 234363790337003665 955 240033396260090176 956 245837189098571354 957 251778260843914987 958 257859803717875289 959 264085051752031293 960 270457342800185479 961 276980058938084592 962 283656690776286973 963 290490775514514718 964 297485962611536789 965 304645950962478671 966 311974556719324425 967 319475647973836434 968 327153214370657223 969 335011300444773791 970 343054077664446000 971 351285775267334040 972 359710753989864891 973 368333435613196668 974 377158379254139947 975 386190208249797479 976 395433688119821893 977 404893652311749314 978 414575082809215379 979 424483032812819586 980 434622709553690354 981 444999395442079390 982 455618533648152427 983 466485646437714507 984 477606422599430374 985 488986634346003309 986 500632227811507086 987 512549236743448974 988 524743875111717209 989 537222449277862567 990 549991453815138840 991 563057480164314768 992 576427314952992319 993 590107846972808662 994 604106168583060291 995 618429479497171630 996 633085190449315771 997 648080825175416506 998 663424127821417986 999 679122960995840046 1000 695185415791333505