0 1 1 1 2 0 3 2 4 1 5 2 6 2 7 2 8 4 9 4 10 6 11 4 12 8 13 6 14 10 15 12 16 15 17 14 18 18 19 20 20 22 21 30 22 30 23 36 24 40 25 51 26 50 27 66 28 66 29 80 30 86 31 102 32 108 33 130 34 138 35 164 36 182 37 200 38 224 39 250 40 280 41 306 42 352 43 378 44 428 45 470 46 530 47 566 48 660 49 703 50 792 51 854 52 960 53 1034 54 1172 55 1264 56 1402 57 1520 58 1688 59 1828 60 2036 61 2206 62 2412 63 2656 64 2893 65 3162 66 3460 67 3774 68 4090 69 4492 70 4858 71 5318 72 5764 73 6308 74 6786 75 7456 76 8012 77 8772 78 9464 79 10316 80 11110 81 12138 82 13034 83 14196 84 15298 85 16620 86 17868 87 19420 88 20872 89 22612 90 24374 91 26348 92 28344 93 30638 94 32966 95 35532 96 38300 97 41200 98 44346 99 47762 100 51389 101 55164 102 59414 103 63720 104 68546 105 73558 106 79082 107 84664 108 91092 109 97454 110 104736 111 112094 112 120344 113 128632 114 138122 115 147562 116 158252 117 169166 118 181258 119 193504 120 207424 121 221337 122 236898 123 252916 124 270476 125 288498 126 308500 127 328978 128 351380 129 374834 130 400072 131 426420 132 454998 133 484882 134 516904 135 550954 136 586928 137 625092 138 665826 139 708924 140 754564 141 803468 142 854550 143 909488 144 967144 145 1028858 146 1093386 147 1163164 148 1235476 149 1313524 150 1395038 151 1482558 152 1573608 153 1672262 154 1774210 155 1884284 156 1998914 157 2122084 158 2250134 159 2388404 160 2531636 161 2685754 162 2846342 163 3018488 164 3197654 165 3390386 166 3590480 167 3804830 168 4029104 169 4268009 170 4517762 171 4784608 172 5063042 173 5359618 174 5670890 175 6000810 176 6347072 177 6714792 178 7100380 179 7508552 180 7938670 181 8392082 182 8869736 183 9374406 184 9905284 185 10464808 186 11055860 187 11676560 188 12332170 189 13021700 190 13749404 191 14512984 192 15321436 193 16167688 194 17062902 195 18001966 196 18993977 197 20032586 198 21132822 199 22282498 200 23499220 201 24772930 202 26118982 203 27526780 204 29017094 205 30573526 206 32219420 207 33941296 208 35759842 209 37660908 210 39671396 211 41770504 212 43987814 213 46307468 214 48753966 215 51312304 216 54012874 217 56834576 218 59809764 219 62923708 220 66202332 221 69633078 222 73247156 223 77026822 224 81004538 225 85170338 226 89548012 227 94132388 228 98952588 229 103997514 230 109296736 231 114850114 232 120676082 233 126781186 234 133188452 235 139899424 236 146936076 237 154314318 238 162043048 239 170145698 240 178635766 241 187532690 242 196847944 243 206618468 244 216839458 245 227558110 246 238774270 247 250530770 248 262826148 249 275722274 250 289200452 251 303333332 252 318109072 253 333594860 254 349777050 255 366746968 256 384468975 257 403046880 258 422456454 259 442792758 260 464031710 261 486293140 262 509531786 263 533880794 264 559307816 265 585936326 266 613735872 267 642855634 268 673245914 269 705067636 270 738289242 271 773057326 272 809347654 273 847333918 274 886971832 275 928446192 276 971737852 277 1017011838 278 1064263808 279 1113683530 280 1165250248 281 1219162156 282 1275432058 283 1334235044 284 1395601290 285 1459734080 286 1526647538 287 1596551226 288 1669508178 289 1745691153 290 1825190372 291 1908208680 292 1994823804 293 2085242956 294 2179601210 295 2278065168 296 2380804146 297 2488015546 298 2599862602 299 2716542316 300 2838288830 301 2965251776 302 3097710396 303 3235846812 304 3379934686 305 3530160110 306 3686877818 307 3850220630 308 4020600240 309 4198184750 310 4383381880 311 4576367980 312 4777644180 313 4987331502 314 5205992892 315 5433796638 316 5671300782 317 5918684560 318 6176620014 319 6445223058 320 6725237110 321 7016838456 322 7320764222 323 7637216448 324 7967047980 325 8310406820 326 8668222128 327 9040720174 328 9428823716 329 9832793446 330 10253683892 331 10691707076 332 11147998356 333 11622875954 334 12117455448 335 12632116604 336 13168114432 337 13725791778 338 14306492262 339 14910691134 340 15539705432 341 16194100260 342 16875342766 343 17583979452 344 18321564948 345 19088821276 346 19887263370 347 20717735424 348 21581923668 349 22480666550 350 23415744674 351 24388218844 352 25399817770 353 26451772404 354 27545985586 355 28683718932 356 29866970532 357 31097280278 358 32376590924 359 33706648530 360 35089601632 361 36527247899 362 38021844428 363 39575538344 364 41190514114 365 42869186116 366 44613963032 367 46427352546 368 48311897512 369 50270508746 370 52305665938 371 54420603584 372 56618066214 373 58901421990 374 61273571736 375 63738368804 376 66298654604 377 68958673010 378 71721594648 379 74591819890 380 77572727204 381 80669286250 382 83884837482 383 87224816692 384 90692951552 385 94294890484 386 98034625628 387 101918459854 388 105950402156 389 110137279570 390 114483593788 391 118996424208 392 123680626078 393 128544035250 394 133591573574 395 138831690344 396 144269922634 397 149915012810 398 155772979492 399 161853422282 400 168162508637 401 174710534112 402 181504454788 403 188554912934 404 195869479604 405 203459775726 406 211333643728 407 219503497884 408 227978170534 409 236770473302 410 245890044748 411 255350804652 412 265162819136 413 275340927620 414 285896407982 415 296844573766 416 308197739706 417 319972486174 418 332181754462 419 344843163836 420 357971169174 421 371583951444 422 385697276552 423 400330791972 424 415501110412 425 431229094452 426 447533208890 427 464434998278 428 481954582108 429 500115177690 430 518938050892 431 538447833496 432 558668052386 433 579624194108 434 601341798518 435 623848337576 436 647170809848 437 671338384464 438 696380793974 439 722328255574 440 749212993296 441 777067538278 442 805925971062 443 835822890760 444 866795622950 445 898880115964 446 932116687850 447 966544069340 448 1002204907760 449 1039140404364 450 1077397088358 451 1117017882716 452 1158052907728 453 1200548461770 454 1244557491282 455 1290129337828 456 1337321523910 457 1386185622356 458 1436783460442 459 1489170649534 460 1543412481282 461 1599568300660 462 1657708796760 463 1717896211370 464 1780206286716 465 1844706218364 466 1911475905628 467 1980587167088 468 2052126252174 469 2126168662802 470 2202806640576 471 2282121711082 472 2364211112376 473 2449162113268 474 2537079339852 475 2628054799196 476 2722200169164 477 2819614808392 478 2920416398884 479 3024711334030 480 3132625986702 481 3244272733746 482 3359786258684 483 3479287963648 484 3602919613219 485 3730811295276 486 3863114969970 487 3999968276842 488 4141532974242 489 4287957623248 490 4439412508342 491 4596056812084 492 4758072753956 493 4925629034684 494 5098919377120 495 5278125738394 496 5463452046218 497 5655093254644 498 5853267318120 499 6058180951790 500 6270065787638 501 6489144530116 502 6715661026718 503 6949853852780 504 7191983320842 505 7442302545232 506 7701088031692 507 7968612186968 508 8245166216718 509 8531041667566 510 8826549270516 511 9131998354882 512 9447718903496 513 9774043456370 514 10111319652994 515 10459903109992 516 10820164620466 517 11192481478386 518 11577247469360 519 11974867568176 520 12385756937920 521 12810348237826 522 13249084138694 523 13702423655618 524 14170836845808 525 14654815792470 526 15154856366146 527 15671483793194 528 16205226823048 529 16756642290639 530 17326291863846 531 17914771666842 532 18522674642800 533 19150636518064 534 19799289349096 535 20469306938206 536 21161360821444 537 21876171399206 538 22614448168174 539 23376958528796 540 24164458833194 541 24977762022094 542 25817671896104 543 26685056629554 544 27580765900722 545 28505723739304 546 29460835917668 547 30447080840452 548 31465421340596 549 32516900984430 550 33602538314704 551 34723443006168 552 35880700762462 553 37075486190174 554 38308953388468 555 39582353949920 556 40896909420144 557 42253949632794 558 43654776594244 559 45100797245814 560 46593395847916 561 48134070144408 562 49724285836600 563 51365633375116 564 53059674552544 565 54808091537214 566 56612544791024 567 58474823591040 568 60396686706960 569 62380032829794 570 64426735796904 571 66538803102342 572 68718226810144 573 70967140865300 574 73287655503686 575 75682034192968 576 78152524360520 577 80701518741236 578 83331406308302 579 86044728748986 580 88844017171030 581 91731966264796 582 94711270728018 583 97784778871384 584 100955354210758 585 104226020913294 586 107599812853544 587 111079935160096 588 114669616536766 589 118372244299320 590 122191248513028 591 126130224033488 592 130192804706246 593 134382799652598 594 138704073975564 595 143160653271938 596 147756642190024 597 152496311513970 598 157384009227570 599 162424259398114 600 167621684620596 601 172981065944076 602 178507310509780 603 184205489298474 604 190080798972276 605 196138610547666 606 202384445962846 607 208823981441988 608 215463076528756 609 222307749897096 610 229364205495432 611 236638817129732 612 244138173616386 613 251869011399198 614 259838318757828 615 268053237240888 616 276521163803828 617 285249660617284 618 294246579361820 619 303519912655938 620 313077984708172 621 322929267098698 622 333082568269378 623 343546858139648 624 354331481517634 625 365445919328565 626 376900074453670 627 388703994333060 628 400868154896896 629 413403193347964 630 426320218048284 631 439630472618534 632 453345723690102 633 467477884994344 634 482039400033290 635 497042880828508 636 512501515601280 637 528428635750278 638 544838205452860 639 561744347803380 640 579161826345020 641 597105590255920 642 615591279441002 643 634634696031594 644 654252393324326 645 674461109154624 646 695278339406170 647 716721798906134 648 738810014292932 649 761561710312670 650 784996488747608 651 809134179189940 652 833995494223286 653 859601418270984 654 885973875075084 655 913135044421216 656 941108114404798 657 969916568827612 658 999584904137586 659 1030137967451752 660 1061601678280854 661 1094002297065172 662 1127367229551840 663 1161724274382778 664 1197102376693758 665 1233530944036680 666 1271040592535456 667 1309662399319916 668 1349428727210758 669 1390372465280382 670 1432527787741762 671 1475929480169132 672 1520613678507942 673 1566617138964648 674 1613978048446120 675 1662735297112242 676 1712929201430897 677 1764600885477818 678 1817792968456220 679 1872548897015466 680 1928913698978270 681 1986933331015902 682 2046655324379296 683 2108128264829756 684 2171402384667532 685 2236529005466764 686 2303561186663594 687 2372553200234134 688 2443561047270484 689 2516642090256846 690 2591855498959276 691 2669261854385236 692 2748923644120978 693 2830904914474926 694 2915271607354814 695 3002091399687308 696 3091433949115510 697 3183370715746726 698 3277975249817458 699 3375323076920534 700 3475491803473162 701 3578561215894172 702 3684613276583776 703 3793732215252540 704 3906004558554956 705 4021519303344312 706 4140367736318666 707 4262643851011656 708 4388444039690196 709 4517867508254510 710 4651016000530292 711 4787994306975414 712 4928909755730422 713 5073872992365078 714 5222997325931592 715 5376399512956286 716 5534199133615108 717 5696519482467744 718 5863486688338032 719 6035230900408992 720 6211885252523140 721 6393587051829982 722 6580476778468232 723 6772699388729970 724 6970403037271378 725 7173740701068550 726 7382868734930448 727 7597948494313164 728 7819144936837036 729 8046628359354978 730 8280572710328914 731 8521157664852612 732 8768566767012518 733 9022989492489630 734 9284619452580416 735 9553656571081008 736 9830304985732034 737 10114775578795568 738 10407283712112290 739 10708051722920878 740 11017306749886940 741 11335283330630522 742 11662220922043834 743 11998366859991732 744 12343973721201484 745 12699302224600184 746 13064618715121070 747 13440198150820914 748 13826321283855824 749 14223278009244316 750 14631364409163972 751 15050886003487656 752 15482154962868978 753 15925493417934876 754 16381230377467070 755 16849705398496068 756 17331265391228088 757 17826268145680994 758 18335079361536552 759 18858076194958038 760 19395644014934920 761 19948180297131600 762 20516091303735156 763 21099795776616236 764 21699721906576300 765 22316311006249302 766 22950014227481966 767 23601296565187840 768 24270633542832052 769 24958514945039630 770 25665441874730084 771 26391930409224378 772 27138508439036178 773 27905719631647702 774 28694120287059778 775 29504282959338560 776 30336793767103042 777 31192255880182832 778 32071286650818978 779 32974521374338636 780 33902610503576510 781 34856222976753914 782 35836043987376460 783 36842778109710844 784 37877146927872077 785 38939892410831410 786 40031774684248646 787 41153574882993252 788 42306093584615966 789 43490153382712564 790 44706597232293678 791 45956291234527802 792 47240123195996088 793 48559004794006746 794 49913870906235060 795 51305681427165952 796 52735420551283174 797 54204098772015888 798 55712752450432600 799 57262445088733160 800 58854267793053012 801 60489340118196530 802 62168810529585826 803 63893857404383992 804 65665689844650366 805 67485547858662506 806 69354704180113628 807 71274463951539348 808 73246166583595048 809 75271185568381686 810 77350930763216118 811 79486847282364986 812 81680418904313916 813 83933166400806138 814 86246651009051878 815 88622472892172692 816 91062275085145942 817 93567740947021116 818 96140599342883638 819 98782621471355726 820 101495626136685058 821 104281476711271874 822 107142086929853682 823 110079416762501074 824 113095479543982712 825 116192337189401308 826 119372107405767242 827 122636959076169800 828 125989120024443144 829 129430871237454080 830 132964556063950012 831 136592573751609014 832 140317388709764830 833 144141524269470448 834 148067572503862040 835 152098186789177164 836 156236093125294456 837 160484082016918066 838 164845019811868746 839 169321840882725936 840 173917559520063560 841 178635260879625531 842 183478114439098166 843 188449364292114356 844 193552342538996340 845 198790460011035162 846 204167220166521702 847 209686208586852384 848 215351108470699910 849 221165689524886454 850 227133823298491560 851 233259472649170752 852 239546707517419596 853 245999693193784336 854 252622707695320664 855 259420129528675590 856 266396454753166268 857 273556285522922404 858 280904347487717344 859 288445477185228586 860 296184641044803484 861 304126922390837204 862 312277539956815702 863 320641835907106038 864 329225294548378448 865 338033529303783396 866 347072302976355774 867 356347514501965386 868 365865218508030158 869 375631613355248892 870 385653060743278896 871 395936072815946910 872 406487333259375924 873 417313684384230106 874 428422147256378808 875 439819910410089480 876 451514349814050212 877 463513016806131090 878 475823659471178138 879 488454210769111828 880 501412808674604278 881 514707786294602774 882 528347691621448474 883 542341277051667306 884 556697520439696458 885 571425615089294744 886 586534989232783934 887 602035298432573992 888 617936444423554008 889 634248567105579186 890 650982064589702936 891 668147585940456592 892 685756049308852146 893 703818637529847536 894 722346815342284702 895 741352324811257574 896 760847203620672282 897 780843781562623122 898 801354696555468526 899 822392894452522484 900 843971643880831140 901 866104536098730286 902 888805500797232772 903 912088807348488972 904 935969077946649502 905 960461292694568530 906 985580801272292260 907 1011343328308239804 908 1037764985916283660 909 1064862280773068760 910 1092652123637674964 911 1121151840767592688 912 1150379181706566292 913 1180352331204869400 914 1211089917793240218 915 1242611027755810388 916 1274935210304353370 917 1308082496417739960 918 1342073402041671204 919 1376928947615601122 920 1412670662057144548 921 1449320604628999562 922 1486901365192956038 923 1525436091456637928 924 1564948487034129846 925 1605462839565019208 926 1647004019575196640 927 1689597511222958318 928 1733269407127823620 929 1778046444976304770 930 1823956000028168436 931 1871026122692152076 932 1919285531951310918 933 1968763655795552764 934 2019490620358172766 935 2071497296694418108 936 2124815287490037758 937 2179476974877117816 938 2235515508264884184 939 2292964855166360656 940 2351859784592986104 941 2412235924631225762 942 2474129743416666928 943 2537578607727766116 944 2602620765379511440 945 2669295406958666242 946 2737642643667439180 947 2807703576187739784 948 2879520270216001530 949 2953135826202881480 950 3028594356782853728 951 3105941059655788132 952 3185222190487273100 953 3266485143220840604 954 3349778420873885358 955 3435151716544680106 956 3522655886654800654 957 3612343035047585302 958 3704266481826419692 959 3798480855090085366 960 3895042058054940542 961 3994007361125170011 962 4095435372232948568 963 4199386131819140228 964 4305921079000824056 965 4415103154375277982 966 4526996764939238960 967 4641667886795676558 968 4759184034213932224 969 4879614364940864504 970 5003029645510516562 971 5129502364421672808 972 5259106696865710878 973 5391918617233505848 974 5528015869066573530 975 5667478079812006032 976 5810386727528316024 977 5956825263507811236 978 6106879079216524938 979 6260635627518817430 980 6418184396179803742 981 6579617030806445702 982 6745027305800696260 983 6914511255080491238 984 7088167144216136150 985 7266095598976896042 986 7448399585488906970 987 7635184539916410712 988 7826558346897244248 989 8022631476818793504 990 8223516966625052708 991 8429330553949555140 992 8640190667652181668 993 8856218562397996958 994 9077538308410484084 995 9304276933484623496 996 9536564416377879250 997 9774533824669824182 998 10018321319763171916 999 10268066294399885474 1000 10523911378022856064