0 1 1 0 2 2 3 2 4 1 5 2 6 3 7 2 8 4 9 6 10 6 11 6 12 9 13 8 14 13 15 14 16 15 17 18 18 23 19 22 20 29 21 34 22 35 23 44 24 52 25 52 26 65 27 74 28 80 29 92 30 110 31 114 32 134 33 152 34 164 35 188 36 215 37 230 38 266 39 296 40 321 41 362 42 412 43 438 44 503 45 558 46 602 47 674 48 755 49 810 50 912 51 1010 52 1093 53 1210 54 1346 55 1446 56 1614 57 1772 58 1922 59 2118 60 2334 61 2512 62 2779 63 3044 64 3288 65 3614 66 3963 67 4260 68 4685 69 5108 70 5518 71 6024 72 6586 73 7082 74 7741 75 8414 76 9071 77 9874 78 10738 79 11548 80 12572 81 13618 82 14663 83 15902 84 17245 85 18512 86 20095 87 21712 88 23332 89 25234 90 27278 91 29260 92 31641 93 34122 94 36621 95 39490 96 42579 97 45616 98 49204 99 52922 100 56733 101 61042 102 65652 103 70254 104 75582 105 81148 106 86844 107 93266 108 100103 109 106978 110 114844 111 123064 112 131541 113 140966 114 151036 115 161228 116 172717 117 184776 118 197238 119 211014 120 225658 121 240634 122 257331 123 274842 124 293019 125 312964 126 334171 127 355906 128 380007 129 405286 130 431552 131 460242 132 490682 133 522052 134 556513 135 592764 136 630474 137 671422 138 714857 139 759736 140 808780 141 860310 142 914089 143 972208 144 1033740 145 1097530 146 1166838 147 1239730 148 1315793 149 1397806 150 1484506 151 1574524 152 1671935 153 1774356 154 1881386 155 1996296 156 2117788 157 2244108 158 2380194 159 2523324 160 2672956 161 2833210 162 3002373 163 3178628 164 3367808 165 3566686 166 3774757 167 3996982 168 4231443 169 4475846 170 4737548 171 5012542 172 5300267 173 5606938 174 5930184 175 6267492 176 6627546 177 7005976 178 7401952 179 7823036 180 8266634 181 8729750 182 9223024 183 9741120 184 10283507 185 10859166 186 11465059 187 12097978 188 12770619 189 13476984 190 14216281 191 14999856 192 15823942 193 16684936 194 17598346 195 18557104 196 19560653 197 20622468 198 21738721 199 22905100 200 24140246 201 25436332 202 26792752 203 28226086 204 29731693 205 31305378 206 32969193 207 34714234 208 36540380 209 38467546 210 40490836 211 42605352 212 44838222 213 47179008 214 49627981 215 52209586 216 54918265 217 57749162 218 60734387 219 63862958 220 67135313 221 70581018 222 74194483 223 77970524 224 81948011 225 86114364 226 90471596 227 95054980 228 99858698 229 104878076 230 110159473 231 115689542 232 121471068 233 127547598 234 133912745 235 140562302 236 147552337 237 154868274 238 162515047 239 170544664 240 178951962 241 187733040 242 196955101 243 206603344 244 216684843 245 227262948 246 238332665 247 249892610 248 262022688 249 274707808 250 287958921 251 301852196 252 316384605 253 331556410 254 347464705 255 364093910 256 381459508 257 399654230 258 418676994 259 438532092 260 459335130 261 481072940 262 503766155 263 527526780 264 552358034 265 578268728 266 605398252 267 633734888 268 663308622 269 694253856 270 726579050 271 760300648 272 795585462 273 832426426 274 870862928 275 911059186 276 953029972 277 996801216 278 1042574128 279 1090347214 280 1140174197 281 1192252384 282 1246608520 283 1303280008 284 1362508530 285 1424302584 286 1488732835 287 1556038820 288 1626259944 289 1699452412 290 1775905341 291 1855640066 292 1938750959 293 2025527032 294 2116027195 295 2210328464 296 2308780911 297 2411422190 298 2518375769 299 2629992566 300 2746355358 301 2867571162 302 2994059449 303 3125884404 304 3263205054 305 3406445990 306 3555723593 307 3711181550 308 3873326044 309 4042251966 310 4218168278 311 4401587052 312 4592666798 313 4791600976 314 4998998136 315 5214997244 316 5439865372 317 5674225818 318 5918289513 319 6172311896 320 6437027898 321 6712631506 322 6999467012 323 7298286872 324 7609375329 325 7933064598 326 8270240391 327 8621171298 328 8986295960 329 9366527552 330 9762237581 331 10173862086 332 10602466626 333 11048413780 334 11512264091 335 11995122432 336 12497476035 337 13019885148 338 13563639644 339 14129219776 340 14717336570 341 15329331020 342 15965833386 343 16627565430 344 17316080642 345 18032017236 346 18776271195 347 19550467264 348 20355420430 349 21192051344 350 22062237661 351 22966809274 352 23906901425 353 24884479570 354 25900588128 355 26956401174 356 28054184159 357 29195015328 358 30380318070 359 31612480130 360 32892829940 361 34222854816 362 35605294011 363 37041533340 364 38533360694 365 40083665386 366 41694141281 367 43366661552 368 45104534966 369 46909538532 370 48783906366 371 50731142684 372 52753385511 373 54852998608 374 57033974877 375 59298576172 376 61649594382 377 64091272876 378 66626309942 379 69257664570 380 71990169121 381 74826684602 382 77770687028 383 80827321174 384 83999973817 385 87292348870 386 90710279511 387 94257384920 388 97937978449 389 101758291368 390 105722569621 391 109835429036 392 114103921751 393 118532591250 394 123126795634 395 127894074710 396 132839730049 397 137969508364 398 143291926469 399 148812681136 400 154538396518 401 160478211284 402 166638721040 403 173027056800 404 179653512544 405 186525199002 406 193650303826 407 201039880128 408 208702132998 409 216645884620 410 224883567880 411 233424043094 412 242277402234 413 251457023956 414 260973068771 415 270836449888 416 281062172940 417 291661240428 418 302646081618 419 314032873096 420 325834185205 421 338063466226 422 350738845797 423 363873943628 424 377484033874 425 391588680862 426 406203391214 427 421344723482 428 437034549027 429 453289713890 430 470128949254 431 487575897196 432 505649662393 433 524370582780 434 543765053862 435 563853836460 436 584659894377 437 606211774636 438 628532959591 439 651648401140 440 675589929002 441 700383096346 442 726055982143 443 752643069816 444 780173159727 445 808676802832 446 838192382736 447 868751272928 448 900387780720 449 933143504982 450 967053741404 451 1002155825186 452 1038496011724 453 1076112766552 454 1115047930990 455 1155351685590 456 1197067176666 457 1240239997864 458 1284925852454 459 1331171803612 460 1379028831887 461 1428557417992 462 1479810248786 463 1532842879862 464 1587722399875 465 1644506279700 466 1703256539386 467 1764046053520 468 1826939040485 469 1892003128844 470 1959319034280 471 2028956867106 472 2100991965988 473 2175512072268 474 2252595368203 475 2332324044126 476 2414795191534 477 2500094158200 478 2588312395494 479 2679555464192 480 2773918395158 481 2871500969458 482 2972419888958 483 3076778930952 484 3184688918379 485 3296276823880 486 3411657981983 487 3530953356060 488 3654303167332 489 3781833395344 490 3913678218040 491 4049990209698 492 4190909218597 493 4336581685852 494 4487175974312 495 4642844834984 496 4803750507638 497 4970076254652 498 5141991368647 499 5319672982684 500 5503323107918 501 5693126688018 502 5889279706077 503 6092002111488 504 6301498632330 505 6517983207714 506 6741698140900 507 6972867042442 508 7211726374402 509 7458539979726 510 7713555107771 511 7977029906852 512 8249254755910 513 8530499753986 514 8821049872442 515 9121221372088 516 9431312545456 517 9751634504328 518 10082535076388 519 10424340041688 520 10777392552240 521 11142071420326 522 11518736083047 523 11907761118918 524 12309562866113 525 12724533864926 526 13153086816585 527 13595675236212 528 14052731731428 529 14524706790546 530 15012098480995 531 15515379206130 532 16035044878760 533 16571637987560 534 17125678738943 535 17697708325464 536 18288322169272 537 18898088210018 538 19527601718920 539 20177511240460 540 20848441560240 541 21541042286062 542 22256024724550 543 22994070907278 544 23755894737878 545 24542270972764 546 25353949306914 547 26191708606410 548 27056398166573 549 27948836141026 550 28869877864249 551 29820448292204 552 30801446049482 553 31813804164034 554 32858535900521 555 33936621824912 556 35049085734495 557 36197031109340 558 37381534100825 559 38603711303444 560 39864770893973 561 41165886800112 562 42508283478636 563 43893276447944 564 45322153184308 565 46796248802876 566 48317002867269 567 49885819533360 568 51504161804056 569 53173597048962 570 54895664082835 571 56671957819744 572 58504192459666 573 60394045886004 574 62343264695751 575 64353714904558 576 66427234201764 577 68565726119494 578 70771230482419 579 73045750493086 580 75391369453303 581 77810307530478 582 80304757211307 583 82876988555570 584 85529427203406 585 88264462539230 586 91084577470039 587 93992411663290 588 96990578728899 589 100081783351010 590 103268908224140 591 106554800787346 592 109942417692082 593 113434895348328 594 117035346613258 595 120746991444514 596 124573253261624 597 128517522624552 598 132583317387826 599 136774361618804 600 141094359763237 601 145547141980368 602 150136771304454 603 154867281385180 604 159742854653107 605 164767909919498 606 169946851932186 607 175284233124384 608 180784872387471 609 186453564598768 610 192295278173036 611 198315253011600 612 204518722224477 613 210911092360624 614 217498075169223 615 224285365659894 616 231278861520955 617 238484771977782 618 245909309563900 619 253558890107176 620 261440279169532 621 269560235588736 622 277925754672515 623 286544189630436 624 295422909691962 625 304569522794650 626 313992037476879 627 323698468740300 628 333697107688417 629 343996656482398 630 354605849863651 631 365533702303228 632 376789687864454 633 388383303750078 634 400324369520221 635 412623177233804 636 425290072196415 637 438335727723926 638 451771344136871 639 465608166704672 640 479857816629286 641 494532458421386 642 509644335946687 643 525206077247200 644 541230915259566 645 557732154825754 646 574723539780098 647 592219438462192 648 610234330990342 649 628783147544048 650 647881512547492 651 667545156319640 652 687790321171325 653 708633968136362 654 730093209548721 655 752185684785470 656 774929830598339 657 798344231367612 658 822448068923766 659 847261351885996 660 872804289300418 661 899097706665306 662 926163345634253 663 954023147094066 664 982699748609996 665 1012216739544960 666 1042597968956724 667 1073868007434974 668 1106052478024831 669 1139177266101688 670 1173269069612194 671 1208355682091672 672 1244465229140722 673 1281626679829008 674 1319870213477550 675 1359226347922562 676 1399726548552210 677 1441403542515632 678 1484290476085371 679 1528421481663036 680 1573832083018600 681 1620558235554384 682 1668636998761941 683 1718106885596118 684 1769006933346015 685 1821377331278230 686 1875259869237060 687 1930696880253498 688 1987731984518944 689 2046410476192308 690 2106778300085325 691 2168882746598166 692 2232772947356074 693 2298498711816972 694 2366111348760353 695 2435664096280418 696 2507210993625634 697 2580807651136790 698 2656511798156663 699 2734382002697556 700 2814478579400850 701 2896864065940296 702 2981601981863457 703 3068757679571212 704 3158398950689516 705 3250594618150564 706 3345415538468592 707 3442935130665560 708 3543228009896959 709 3646370929867332 710 3752443451849232 711 3861526398040992 712 3973702958161564 713 4089059275499804 714 4207682944734574 715 4329664053623816 716 4455095923313429 717 4584073408041008 718 4716694117520949 719 4853059066687662 720 4993271023901625 721 5137435663470764 722 5285662382896744 723 5438062436994092 724 5594750285642873 725 5755844315001194 726 5921465022655028 727 6091736291224526 728 6266786291928774 729 6446745436030698 730 6631747863121862 731 6821932239142064 732 7017439764428171 733 7218415581395560 734 7425009772108432 735 7637375111851304 736 7855668710160310 737 8080052896545008 738 8310693032705270 739 8547759069185934 740 8791426647264519 741 9041874635334324 742 9299286939733252 743 9563853485418012 744 9835767817341886 745 10115228818730466 746 10402441929298643 747 10697616445451682 748 11000967516605560 749 11312717232739618 750 11633091993569444 751 11962324408111192 752 12300654638464326 753 12648327443940116 754 13005594382238091 755 13372715013789800 756 13749954019722474 757 14137583298858628 758 14535883453416525 759 14945140551254188 760 15365648553929638 761 15797710651076584 762 16241636103107344 763 16697742557912384 764 17166357690620799 765 17647815662579690 766 18142459795901892 767 18650644053320688 768 19172729582018066 769 19709087270777630 770 20260099562026188 771 20826156578181782 772 21407659071326538 773 22005020060685330 774 22618661052914992 775 23249014865179736 776 23896527625566519 777 24561654540179388 778 25244863142658868 779 25946635110347532 780 26667462129148406 781 27407849011482166 782 28168315905653477 783 28949393670702292 784 29751627458490890 785 30575578724600160 786 31421820711399664 787 32290941887119700 788 33183548387887963 789 34100258967721246 790 35041708944559605 791 36008552429616322 792 37001457392583014 793 38021109459426976 794 39068214607243092 795 40143493655321852 796 41247686612877885 797 42381555148187240 798 43545877203338247 799 44741451183889494 800 45969098938159362 801 47229659746273660 802 48523995112253937 803 49852991500054028 804 51217554457600511 805 52618613241619628 806 54057124107423206 807 55534063759485316 808 57050434627917010 809 58607267902669050 810 60205617127234337 811 61846563300736182 812 63531218514343491 813 65260718814860120 814 67036230020341659 815 68858951079716048 816 70730107094950770 817 72650954950770682 818 74622787331636306 819 76646924953988222 820 78724722971140270 821 80857574700034812 822 83046904019863899 823 85294171586352268 824 87600879271131438 825 89968561708770170 826 92398793354498818 827 94893192613487218 828 97453413572332279 829 100081152852228516 830 102778154518557079 831 105546200889529318 832 108387120309874526 833 111302791730890334 834 114295135716796705 835 117366122009839524 836 120517774954020195 837 123752163510191360 838 127071409820143311 839 130477694283629580 840 133973245787074901 841 137560350048797670 842 141241355619616254 843 145018663036007508 844 148894734258373534 845 152872098301602652 846 156953340622480906 847 161141112330528912 848 165438136821749418 849 169847198011763558 850 174371150730312257 851 179012926970061160 852 183775524370473682 853 188662016380261918 854 193675559597650800 855 198819381007900852 856 204096789440579543 857 209511182497509646 858 215066034069087201 859 220764905549317322 860 226611453955046164 861 232609418099104030 862 238762631212775482 863 245075028637818684 864 251550634295856198 865 258193573069669252 866 265008079788238389 867 271998484253398100 868 279169225153050189 869 286524858595535410 870 294070043466160918 871 301809555087849636 872 309748295170718788 873 317891275612154596 874 326243633829191290 875 334810642235780838 876 343597692400242979 877 352610310129866122 878 361854166481322943 879 371335060252347750 880 381058934882442417 881 391031888974078570 882 401260159174364374 883 411750136825144044 884 422508380162249843 885 433541595398829160 886 444856655361795942 887 456460611177372962 888 468360673785428574 889 480564232326923644 890 493078867654670889 891 505912331925417404 892 519072569141900904 893 532567728139682970 894 546406142646680888 895 560596351585803328 896 575147114050040320 897 590067387296643442 898 605366349406413976 899 621053413708259326 900 637138207296200339 901 653630593453038820 902 670540688246658402 903 687878836832303110 904 705655638440935640 905 723881962419165220 906 742568925096149492 907 761727914559505172 908 781370609057091102 909 801508951496714672 910 822155177016534873 911 843321830814690970 912 865021743281687926 913 887268057366326992 914 910074248991665036 915 933454099648056106 916 957421726810735531 917 981991603773586130 918 1007178532936630275 919 1032997676054512288 920 1059464576879578296 921 1086595131745812570 922 1114405623138140714 923 1142912741753754126 924 1172133557852951790 925 1202085554687581506 926 1232786653639593245 927 1264255182671737688 928 1296509913389960224 929 1329570085593478226 930 1363455376580786980 931 1398185938110545944 932 1433782424306085333 933 1470265957879550424 934 1507658171043563895 935 1545981232846048952 936 1585257816335503001 937 1625511139427456420 938 1666764995900836852 939 1709043719274147062 940 1752372227996465484 941 1796776055874094240 942 1842281317006147949 943 1888914750984105308 944 1936703757324542200 945 1985676356902312868 946 2035861241865430403 947 2087287809534378990 948 2139986124998518681 949 2193986971128349196 950 2249321886843470160 951 2306023125992457034 952 2364123712512333908 953 2423657478191594892 954 2484659022861660008 955 2547163769727963352 956 2611208007923786428 957 2676828848746687534 958 2744064286618957865 959 2812953241181056556 960 2883535514985836962 961 2955851854753487636 962 3029943998686228155 963 3105854629985763436 964 3183627444248836015 965 3263307196390064380 966 3344939655786995484 967 3428571674092369408 968 3514251237885974829 969 3602027419380036908 970 3691950450960328082 971 3784071777514157696 972 3878444008965564033 973 3975120995382612254 974 4074157885568837535 975 4175611074924628920 976 4279538287891449852 977 4385998636335797340 978 4495052569449210004 979 4606761956945340130 980 4721190154300126273 981 4838401947714983400 982 4958463645357861263 983 5081443142497680288 984 5207409868774043210 985 5336434880388231588 986 5468590932757593370 987 5603952422586198570 988 5742595488849738702 989 5884598085513170516 990 6030039926168224896 991 6179002586232269298 992 6331569583894416573 993 6487826319301715314 994 6647860186381720152 995 6811760654025905518 996 6979619208183019871 997 7151529465156545176 998 7327587261832373373 999 7507890592046118272 1000 7692539730429717150