1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 10 0 11 1 12 0 13 1 14 0 15 1 16 3 17 1 18 3 19 1 20 3 21 1 22 3 23 7 24 3 25 8 26 3 27 8 28 3 29 8 30 14 31 8 32 17 33 8 34 18 35 8 36 18 37 26 38 18 39 33 40 18 41 36 42 18 43 37 44 47 45 37 46 61 47 37 48 68 49 37 50 71 51 81 52 72 53 106 54 72 55 121 56 72 57 128 58 138 59 131 60 181 61 132 62 209 63 132 64 224 65 228 66 231 67 297 68 234 69 347 70 235 71 376 72 373 73 391 74 482 75 398 76 566 77 401 78 619 79 596 80 648 81 761 82 663 83 898 84 670 85 989 86 944 87 1043 88 1192 89 1072 90 1407 91 1087 92 1559 93 1466 94 1653 95 1828 96 1707 97 2160 98 1736 99 2404 100 2258 101 2563 102 2783 103 2658 104 3282 105 2712 106 3667 107 3424 108 3926 109 4170 110 4088 111 4910 112 4183 113 5500 114 5151 115 5914 116 6205 117 6180 118 7282 119 6343 120 8174 121 7649 122 8818 123 9117 124 9247 125 10667 126 9516 127 11988 128 11275 129 12974 130 13309 131 13647 132 15510 133 14083 134 17444 135 16439 136 18924 137 19227 138 19964 139 22323 140 20652 141 25111 142 23804 143 27304 144 27609 145 28879 146 31918 147 29948 148 35899 149 34148 150 39100 151 39299 152 41455 153 45251 154 43084 155 50866 156 48675 157 55488 158 55621 159 58955 160 63773 161 61405 162 71630 163 68825 164 78224 165 78132 166 83274 167 89225 168 86904 169 100111 170 96745 171 109433 172 109173 173 116697 174 124165 175 122016 176 139144 177 135036 178 152194 179 151547 180 162549 181 171694 182 170248 183 192139 184 187461 185 210265 186 209332 187 224875 188 236252 189 235915 190 263989 191 258625 192 288961 193 287475 194 309413 195 323273 196 325085 197 360646 198 355022 199 394815 200 392977 201 423200 202 440348 203 445266 204 490441 205 484654 206 536869 207 534416 208 575993 209 596838 210 606799 211 663588 212 658570 213 726298 214 723655 215 779828 216 805570 217 822528 218 894100 219 890447 220 978292 221 975323 222 1051090 223 1082418 224 1109844 225 1199246 226 1198838 227 1311682 228 1309281 229 1410051 230 1448791 231 1490386 232 1602319 233 1606773 234 1751686 235 1750114 236 1883890 237 1931257 238 1993032 239 2132127 240 2145026 241 2329620 242 2330684 243 2506306 244 2565134 245 2653749 246 2826965 247 2851853 248 3086878 249 3091770 250 3321865 251 3394326 252 3519933 253 3734294 254 3777719 255 4074912 256 4087151 257 4385891 258 4476501 259 4650618 260 4916437 261 4985386 262 5360970 263 5383635 264 5770716 265 5883351 266 6122765 267 6450692 268 6556735 269 7028631 270 7068348 271 7566121 272 7708095 273 8032157 274 8437500 275 8593558 276 9186091 277 9249508 278 9888348 279 10066570 280 10502502 281 11001438 282 11227390 283 11967715 284 12066893 285 12881599 286 13108018 287 13687583 288 14302899 289 14621588 290 15545976 291 15693999 292 16730943 293 17017729 294 17784377 295 18540680 296 18985476 297 20134815 298 20353018 299 21665735 300 22032539 301 23037362 302 23968702 303 24578654 304 26006794 305 26319407 306 27978104 307 28446037 308 29757425 309 30901300 310 31731310 311 33499480 312 33943341 313 36029516 314 36630888 315 38329685 316 39737152 317 40852224 318 43040105 319 43658202 320 46277312 321 47048243 322 49240718 323 50969024 324 52457924 325 55156805 326 56011344 327 59286387 328 60279766 329 63092040 330 65217991 331 67186605 332 70514047 333 71678893 334 75767149 335 77043839 336 80639218 337 83250298 338 85839951 339 89931588 340 91509758 341 96595389 342 98241477 343 102814238 344 106026306 345 109406363 346 114435257 347 116550387 348 122866562 349 124983047 350 130781663 351 134728450 352 139120858 353 145287909 354 148107737 355 155928253 356 158654155 357 165974645 358 170831213 359 176502672 360 184062206 361 187789260 362 197457867 363 200958504 364 210175470 365 216146159 366 223440990 367 232689819 368 237593019 369 249514347 370 254012191 371 265572336 372 272921867 373 282254362 374 293565642 375 299970822 376 314649087 377 320411149 378 334874646 379 343914811 380 355813268 381 369624567 382 377956906 383 395986825 384 403365927 385 421400972 386 432532000 387 447632321 388 464490390 389 475265888 390 497383829 391 506805797 392 529243888 393 542940510 394 562045179 395 582593759 396 596476349 397 623552117 398 635571295 399 663404198 400 680270803 401 704345495 402 729384690 403 747180286 404 780284953 405 795572637 406 830026188 407 850783555 408 881036186 409 911511205 410 934244782 411 974645037 412 994064110 413 1036600021 414 1062159036 415 1100042058 416 1137122177 417 1166037209 418 1215285201 419 1239882445 420 1292296775 421 1323748004 422 1371064462 423 1416134926 424 1452797325 425 1512730459 426 1543837113 427 1608270381 428 1646982958 429 1705898611 430 1760665771 431 1806973130 432 1879833314 433 1919065016 434 1998133890 435 2045751422 436 2118937073 437 2185427028 438 2243749052 439 2332191914 440 2381584779 441 2478405633 442 2536979257 443 2627638887 444 2708337969 445 2781541774 446 2888795523 447 2950819683 448 3069184758 449 3141180984 450 3253242942 451 3351108434 452 3442748674 453 3572639038 454 3650382868 455 3794805198 456 3883285415 457 4021455507 458 4140103996 459 4254473794 460 4411635759 461 4508842379 462 4684791526 463 4793440239 464 4963458823 465 5107197399 466 5249585657 467 5439513776 468 5560830882 469 5774810418 470 5908178198 471 6116911271 472 6290990538 473 6467772588 474 6697103873 475 6848156423 476 7108020030 477 7271584770 478 7527369805 479 7738048137 480 7957034363 481 8233637418 482 8421367363 483 8736444905 484 8936941385 485 9249735164 486 9504619646 487 9775205530 488 10108559750 489 10341354411 490 10722876084 491 10968408994 492 11350253186 493 11658415012 494 11992054044 495 12393397435 496 12681551618 497 13142845965 498 13443337848 499 13908589913 500 14281025151 501 14691466750 502 15174304804 503 15530233485 504 16087296939 505 16454680042 506 17020640486 507 17470463301 508 17974394029 509 18554735184 510 18993602567 511 19665401980 512 20114228276 513 20801491930 514 21344558267 515 21961968124 516 22659008049 517 23199064507 518 24008303094 519 24556053835 520 25389355056 521 26044572167 522 26799624269 523 27636109195 524 28299548602 525 29273118721 526 29941036113 527 30949772708 528 31739945120 529 32661526274 530 33664675379 531 34478153066 532 35648166932 533 36461736983 534 37681109515 535 38633419032 536 39756319635 537 40958373597 538 41954174404 539 43358631719 540 44348718966 541 45820499609 542 46967654790 543 48333382192 544 49772847680 545 50989665304 546 52673841018 547 53877422845 548 55651491598 549 57032455425 550 58690833504 551 60413298144 552 61897826204 553 63915242148 554 65376957896 555 67512416698 556 69173969562 557 71184324061 558 73244137648 559 75052221249 560 77466516299 561 79239762710 562 81807006463 563 83804830096 564 86238156303 565 88699624159 566 90898427082 567 93784756133 568 95933802011 569 99016116346 570 101416920817 571 104357590061 572 107297247238 573 109966929646 574 113414484512 575 116016080382 576 119712433439 577 122595547938 578 126144243952 579 129652583174 580 132889250733 581 137003257341 582 140149521170 583 144576834095 584 148037102891 585 152313254978 586 156497803985 587 160415924879 588 165321041779 589 169121794397 590 174418704025 591 178568793928 592 183714550328 593 188702351313 594 193438765647 595 199281913047 596 203868613970 597 210198674932 598 215173017214 599 221356686373 600 227298461597 601 233015828477 602 239970770909 603 245499871155 604 253056624388 605 259014729064 606 266436151414 607 273509830772 608 280402074357 609 288673401058 610 295331706007 611 304343165192 612 311474985166 613 320370363640 614 328786725043 615 337083909211 616 346913212171 617 354922652234 618 365658127790 619 374188777245 620 384837932983 621 394845585563 622 404821300975 623 416492743367 624 426117672933 625 438894020366 626 449091070396 627 461824180466 628 473717198975 629 485695407400 630 499544049444 631 511097981382 632 526288783208 633 538468929177 634 553676314060 635 567801235600 636 582166275575 637 598585822996 638 612441350025 639 630485572824 640 645024546865 641 663166016463 642 679932169333 643 697138302414 644 716592322658 645 733190558468 646 754604896919 647 771946827531 648 793564867618 649 813454138084 650 834039082465 651 857071735046 652 876935779528 653 902326595167 654 922997460743 655 948730129282 656 972310928308 657 996909096419 658 1024160232607 659 1047908326630 660 1077988228604 661 1102608916414 662 1133207587320 663 1161148414474 664 1190509187731 665 1222729147389 666 1251092917960 667 1286697156180 668 1316001699369 669 1352348776255 670 1385437087494 671 1420443078829 672 1458513001997 673 1492355689052 674 1534464404912 675 1569318105171 676 1612450862291 677 1651611821392 678 1693303510529 679 1738255659644 680 1778596795884 681 1828357444409 682 1869781555500 683 1920916368151 684 1967238308960 685 2016839116299 686 2069884175537 687 2117924713520 688 2176681889910 689 2225878644884 690 2286442976923 691 2341203212505 692 2400152653540 693 2462707536200 694 2519863170678 695 2589189169612 696 2647575137332 697 2719240555405 698 2783939701153 699 2853927662685 700 2927652163739 701 2995587812569 702 3077322564959 703 3146563053393 704 3231288083389 705 3307685438460 706 3390696717473 707 3477531433985 708 3558206144890 709 3654498726860 710 3736552785661 711 3836627735080 712 3926787486398 713 4025148461547 714 4127363946999 715 4223078011943 716 4336440055857 717 4433607570348 718 4551711857274 719 4658051405395 720 4774489761904 721 4894738069209 722 5008193427772 723 5141555329196 724 5256537625119 725 5395800433107 726 5521152500739 727 5658860542556 728 5800241066178 729 5934605428369 730 6091387685519 731 6227351744851 732 6391428594263 733 6539106998186 734 6701821594793 735 6867950915957 736 7026938849832 737 7211127952161 738 7371787880288 739 7564942450940 740 7738825465949 741 7930913642576 742 8126013608484 743 8313973492318 744 8530217082081 745 8719921346726 746 8947127594187 747 9151747173317 748 9378312929517 749 9607305028550 750 9829327691429 751 10083036740705 752 10306877479621 753 10573929692666 754 10814583178794 755 11081582826926 756 11350205853114 757 11612242077036 758 11909717656363 759 12173648786468 760 12487297553162 761 12770168331764 762 13084552959698 763 13399490180084 764 13708495970042 765 14057066461387 766 14368050057098 767 14736149898115 768 15068456847840 769 15438327272437 770 15807363392623 771 16171458248642 772 16579647981584 773 16945813660946 774 17377503781216 775 17767663942833 776 18202460370528 777 18634652436623 778 19063313218194 779 19541026275997 780 19971866843578 781 20477768652711 782 20935596831416 783 21446306439202 784 21952192919754 785 22456466385378 786 23015210618219 787 23521796487272 788 24114253513083 789 24651180971492 790 25250589943900 791 25842419830854 792 26435180844184 793 27088313500682 794 27683553675886 795 28376895178516 796 29006235752008 797 29709206617990 798 30401217505054 799 31097453621779 800 31860478496503 801 32559408192865 802 33370267096380 803 34107510409779 804 34931316371606 805 35740040824829 806 36557195527315 807 37448090465097 808 38268218570137 809 39215882464355 810 40079048097712 811 41043742611511 812 41988377442692 813 42946730151513 814 43986340623788 815 44948034427994 816 46054866224801 817 47064895816936 818 48193755302799 819 49296570309798 820 50419691764131 821 51632166579847 822 52759113477432 823 54051017712659 824 55232245476677 825 56552260621188 826 57839088187148 827 59154346554487 828 60567658386152 829 61887379128670 830 63394357664135 831 64775033409456 832 66317494361274 833 67818273539309 834 69357437432007 835 71003961251377 836 72548422267310 837 74305192431582 838 75918105526694 839 77719253494264 840 79468678102808 841 81268588943304 842 83185789420733 843 84992085780130 844 87038813315029 845 88921988657325 846 91023788110962 847 93062029385782 848 95165398425916 849 97396596269797 850 99507762198194 851 101890878986541 852 104088402970703 853 106539403900607 854 108912967019818 855 111369266442909 856 113964544800670 857 116430460250375 858 119203629535747 859 121766573988178 860 124622929142285 861 127385611005540 862 130252125408410 863 133269343136570 864 136147804615645 865 139373000587493 866 142360514188465 867 145687117651678 868 148901137030927 869 152244141722231 870 155750126761823 871 159108047880527 872 162856824817205 873 166337356896237 874 170209181859821 875 173946446186103 876 177842591845300 877 181914478395847 878 185829301976729 879 190184216784159 880 194236956929116 881 198740556051228 882 203084150184045 883 207622017482946 884 212348814845249 885 216910099167666 886 221966377573386 887 226682873066423 888 231918134856123 889 236963993191763 890 242245912940250 891 247730266819698 892 253041544335110 893 258908951822843 894 264395003150167 895 270477125130167 896 276335989612462 897 282480089546395 898 288840341376676 899 295021209985700 900 301826235927823 901 308204029927269 902 315265820870339 903 322065443772253 904 329208036932498 905 336580539592639 906 343769104765953 907 351657418606789 908 359068019878631 909 367262489784674 910 375150204686529 911 383448478682924 912 391990295576727 913 400345921621055 914 409485231638680 915 418091390040979 916 427594763008979 917 436740381121802 918 446375526725135 919 456267470976509 920 465973983945054 921 476557256054896 922 486546675643971 923 497561783179848 924 508160963741559 925 519341701312028 926 530791868046967 927 542061167882909 928 554310361800647 929 565899388470683 930 578659606107971 931 590937657481459 932 603904328233459 933 617152076317823 934 630228330157781 935 644398610359369 936 657836513586550 937 672610198686510 938 686826489671003 939 701855671045407 940 717176238861472 941 732340614048305 942 748725225392953 943 764299032504121 944 781394659847780 945 797847599076556 946 815257445974736 947 832967159105921 948 850543303637048 949 869479071044726 950 887519166041029 951 907291121490658 952 926323921936885 953 946480196133583 954 966942490027047 955 987302722332202 956 1009176404067400 957 1030062853047097 958 1052918122998756 959 1074925313291863 960 1098248345133592 961 1121880564785021 962 1145453024253405 963 1170708482949004 964 1194878342860403 965 1221284065193882 966 1246719010526257 967 1273691561476577 968 1300972808205837 969 1328249535026270 970 1357396004440791 971 1385351584357417 972 1415843748748532 973 1445227150519953 974 1476403472407677 975 1507883467667431 976 1539429716783910 977 1573051137133583 978 1605369523390138 979 1640562796290926 980 1674492489242214 981 1710508559414291 982 1746817853161708 983 1783282622238068 984 1822048381288744 985 1859392207645181 986 1899991231136152 987 1939153259507980 988 1980738551054954 989 2022600057708871 990 2064728199201642 991 2109405266067581 992 2152535107146422 993 2199347262215213 994 2244528622247955 995 2292519405179984 996 2340761665040896 997 2389407579896088 998 2440874441271715 999 2490662828913958 1000 2544612887500055