0 1 1 1 2 0 3 0 4 1 5 1 6 1 7 1 8 1 9 2 10 3 11 2 12 2 13 3 14 4 15 5 16 5 17 4 18 6 19 8 20 8 21 9 22 11 23 11 24 13 25 16 26 17 27 19 28 22 29 23 30 27 31 31 32 32 33 36 34 43 35 47 36 52 37 57 38 61 39 70 40 80 41 84 42 93 43 105 44 114 45 127 46 141 47 150 48 167 49 188 50 202 51 220 52 244 53 264 54 291 55 322 56 346 57 377 58 416 59 450 60 493 61 540 62 580 63 633 64 696 65 750 66 814 67 888 68 957 69 1042 70 1138 71 1222 72 1323 73 1441 74 1553 75 1682 76 1825 77 1961 78 2121 79 2301 80 2474 81 2670 82 2888 83 3102 84 3349 85 3621 86 3883 87 4180 88 4513 89 4843 90 5213 91 5618 92 6018 93 6467 94 6966 95 7465 96 8012 97 8611 98 9219 99 9894 100 10629 101 11366 102 12177 103 13067 104 13975 105 14966 106 16036 107 17128 108 18327 109 19631 110 20962 111 22404 112 23966 113 25574 114 27321 115 29207 116 31143 117 33237 118 35500 119 37840 120 40363 121 43072 122 45871 123 48892 124 52145 125 55515 126 59128 127 63000 128 67024 129 71354 130 75991 131 80794 132 85938 133 91457 134 97204 135 103345 136 109897 137 116722 138 124021 139 131822 140 139950 141 148606 142 157835 143 167479 144 177760 145 188705 146 200123 147 212276 148 225215 149 238742 150 253121 151 268397 152 284362 153 301331 154 319366 155 338224 156 358217 157 379436 158 401651 159 425216 160 450200 161 476334 162 504014 163 533361 164 564100 165 596636 166 631065 167 667119 168 705277 169 745665 170 787955 171 832645 172 879902 173 929422 174 981751 175 1037048 176 1094953 177 1156089 178 1220680 179 1288368 180 1359782 181 1435145 182 1514103 183 1597393 184 1685278 185 1777357 186 1874391 187 1976704 188 2083922 189 2196905 190 2315967 191 2440682 192 2572012 193 2710382 194 2855364 195 3007964 196 3168607 197 3336888 198 3513966 199 3700356 200 3895587 201 4100877 202 4316839 203 4543069 204 4780907 205 5030996 206 5292885 207 5568087 208 5857382 209 6160353 210 6478598 211 6812945 212 7163014 213 7530644 214 7916800 215 8321060 216 8745369 217 9190864 218 9657220 219 10146611 220 10660253 221 11197800 222 11761661 223 12353309 224 12972484 225 13621758 226 14302698 227 15015170 228 15762109 229 16545317 230 17364643 231 18223248 232 19123213 233 20064593 234 21050901 235 22084403 236 23165182 237 24297168 238 25483027 239 26723024 240 28021392 241 29381055 242 30802505 243 32290527 244 33848451 245 35476892 246 37181026 247 38964663 248 40828780 249 42779159 250 44819971 251 46952379 252 49182828 253 51516152 254 53953895 255 56503082 256 59169032 257 61953734 258 64865106 259 67909202 260 71088329 261 74411125 262 77884473 263 81511365 264 85301409 265 89262207 266 93397227 267 97717191 268 102230807 269 106942298 270 111863403 271 117003754 272 122368447 273 127970685 274 133821338 275 139926263 276 146299962 277 152954735 278 159897640 279 167144835 280 174709964 281 182601105 282 190836275 283 199431003 284 208394786 285 217747429 286 227506170 287 237682133 288 248297517 289 259371732 290 270917466 291 282959186 292 295518735 293 308610992 294 322263223 295 336499686 296 351337291 297 366806449 298 382934596 299 399741214 300 417259867 301 435521074 302 454547262 303 474375974 304 495041483 305 516569211 306 539000629 307 562374195 308 586719217 309 612081872 310 638504933 311 666021548 312 694683174 313 724537917 314 755623588 315 787997113 316 821712010 317 856811344 318 893358707 319 931414032 320 971025866 321 1012264584 322 1055197294 323 1099879317 324 1146388980 325 1194800926 326 1245177458 327 1297605747 328 1352169490 329 1408939203 330 1468011421 331 1529479235 332 1593422426 333 1659948629 334 1729161817 335 1801151595 336 1876037224 337 1953934820 338 2034945729 339 2119202572 340 2206834467 341 2297955085 342 2392711922 343 2491249309 344 2593695200 345 2700213005 346 2810963195 347 2926089705 348 3045774428 349 3170196247 350 3299516346 351 3433936250 352 3573655345 353 3718854911 354 3869758864 355 4026588670 356 4189547076 357 4358882827 358 4534842880 359 4717654463 360 4907593199 361 5104933354 362 5309929445 363 5522887820 364 5744113692 365 5973891204 366 6212559737 367 6460458849 368 6717906746 369 6985280000 370 7262955467 371 7551288088 372 7850695725 373 8161597648 374 8484390338 375 8819536549 376 9167501407 377 9528727513 378 9903728503 379 10293021000 380 10697097969 381 11116528112 382 11551885198 383 12003719245 384 12472660636 385 12959345440 386 13464385726 387 13988480109 388 14532334944 389 15096631900 390 15682144090 391 16289654176 392 16919921036 393 17573801503 394 18252163542 395 18955850493 396 19685810316 397 20443005271 398 21228373712 399 22042965145 400 22887845023 401 23764055273 402 24672757664 403 25615133232 404 26592339496 405 27605660946 406 28656404669 407 29745856083 408 30875436865 409 32046594291 410 33260754026 411 34519487344 412 35824396375 413 37177063480 414 38579226118 415 40032655986 416 41539106821 417 43100499461 418 44718794535 419 46395936102 420 48134045907 421 49935291024 422 51801825774 423 53735995299 424 55740195604 425 57816811560 426 59968432520 427 62197706898 428 64507276057 429 66899999653 430 69378802829 431 71946607719 432 74606571846 433 77361927326 434 80215907268 435 83171995612 436 86233760391 437 89404777580 438 92688892919 439 96090045653 440 99612187872 441 103259561151 442 107036513622 443 110947414076 444 114996941227 445 119189891464 446 123531090003 447 128025696521 448 132679003220 449 137496339386 450 142483391908 451 147645995716 452 152990035132 453 158521779428 454 164247662068 455 170174176047 456 176308228199 457 182656910158 458 189227387407 459 196027269316 460 203064368903 461 210346588133 462 217882308573 463 225680139016 464 233748793024 465 242097498244 466 250735734784 467 259673108352 468 268919779064 469 278486185920 470 288382912699 471 298621140198 472 309212360684 473 320168235711 474 331501068625 475 343223505521 476 355348388272 477 367889252505 478 380860014305 479 394274813593 480 408148535815 481 422496487030 482 437334232175 483 452678141151 484 468545047314 485 484952076752 486 501917223866 487 519458997417 488 537596240170 489 556348730233 490 575736810822 491 595781203668 492 616503642701 493 637926486450 494 660072519769 495 682965617257 496 706630342178 497 731091741480 498 756376040088 499 782510219921 500 809521804247 501 837439588679 502 866293205323 503 896112895525 504 926930273530 505 958777871032 506 991688902654 507 1025698069780 508 1060841084429 509 1097154420631 510 1134676156393 511 1173445480990 512 1213502438114 513 1254888807030 514 1297647586488 515 1341822724772 516 1387460046845 517 1434606720778 518 1483310973985 519 1533623061569 520 1585594709848 521 1639278823621 522 1694730504913 523 1752006472037 524 1811164750605 525 1872265739949 526 1935371612689 527 2000545996144 528 2067855088348 529 2137367029836 530 2209151569734 531 2283281239793 532 2359830705498 533 2438876415666 534 2520497829059 535 2604776738794 536 2691796911362 537 2781645376197 538 2874411722027 539 2970187716746 540 3069068657286 541 3171152643463 542 3276540186682 543 3385335622358 544 3497646351701 545 3613582433126 546 3733258067163 547 3856790814219 548 3984301167434 549 4115914104338 550 4251758273705 551 4391965556327 552 4536672696263 553 4686020455345 554 4840153151932 555 4999220368730 556 5163376081773 557 5332778186645 558 5507590285446 559 5687980779681 560 5874122376856 561 6066193968574 562 6264379696626 563 6468868438833 564 6679855771794 565 6897543002278 566 7122136640478 567 7353850462589 568 7592904505725 569 7839524517264 570 8093944114503 571 8356403751229 572 8627150153695 573 8906438581481 574 9194531753612 575 9491699263369 576 9798219954122 577 10114380816412 578 10440476380380 579 10776811199674 580 11123698710843 581 11481460613047 582 11850429477803 583 12230947569242 584 12623366198354 585 13028048456046 586 13445368003283 587 13875708413393 588 14319466033478 589 14777048730892 590 15248875214371 591 15735378041220 592 16237002333335 593 16754205075997 594 17287458263654 595 17837247576444 596 18404071667842 597 18988445470450 598 19590898831474 599 20211975775381 600 20852237967052 601 21512263318338 602 22192645240948 603 22893996273840 604 23616946645288 605 24362143507151 606 25130254746709 607 25921967519932 608 26737987466529 609 27579042699755 610 28445882300432 611 29339275526433 612 30260016005933 613 31208920191916 614 32186826549883 615 33194599953788 616 34233130114899 617 35303330766735 618 36406144272123 619 37542540010313 620 38713513548817 621 39920091486531 622 41163329818282 623 42444313094450 624 43764159492941 625 45124019150744 626 46525073327888 627 47968539739878 628 49455670855529 629 50987753049147 630 52566112193552 631 54192111942140 632 55867152891035 633 57592678445176 634 59370173066663 635 61201161436981 636 63087214626444 637 65029948332756 638 67031022044664 639 69092145509436 640 71215076950847 641 73401622255396 642 75653641774581 643 77973048525119 644 80361807379953 645 82821942208573 646 85355534080398 647 87964720488807 648 90651702845292 649 93418744667895 650 96268170828596 651 99202375439603 652 102223820055240 653 105335032947111 654 108538617378574 655 111837249811025 656 115233679231857 657 118730735864269 658 122331329382198 659 126038448274048 660 129855168993665 661 133784654212294 662 137830152251669 663 141995006698150 664 146282654673705 665 150696626331467 666 155240554979177 667 159918175405578 668 164733323445908 669 169689946615386 670 174792102482346 671 180043958337719 672 185449802395331 673 191014042221408 674 196741204490828 675 202635946767266 676 208703056023987 677 214947448529832 678 221374182239270 679 227988455389269 680 234795606509746 681 241801127482512 682 249010662259878 683 256430007013972 684 264065123868913 685 271922139738588 686 280007346657401 687 288327216257840 688 296888398741888 689 305697723380741 690 314762213757983 691 324089086921059 692 333685754104453 693 343559836780764 694 353719165979537 695 364171783235550 696 374925957521940 697 385990184796131 698 397373189194105 699 409083940861414 700 421131655729354 701 433525797011995 702 446276094023891 703 459392542212915 704 472885404952575 705 486765233379481 706 501042866743679 707 515729434567875 708 530836377561448 709 546375448284059 710 562358713681910 711 578798577174659 712 595707779707993 713 613099402703405 714 630986891345727 715 649384056039904 716 668305075847743 717 687764523091866 718 707777365256449 719 728358968914201 720 749525125697524 721 771292054726085 722 793676407116317 723 816695293399257 724 840366286482377 725 864707426767963 726 889737251140351 727 915474796564940 728 941939605869259 729 969151758348586 730 997131874033074 731 1025901120232749 732 1055481243908709 733 1085894576670385 734 1117164042104801 735 1149313189991272 736 1182366202138737 737 1216347900622712 738 1251283783953266 739 1287200033781217 740 1324123524089634 741 1362081859478718 742 1401103382876351 743 1441217185767030 744 1482453148670643 745 1524841949916678 746 1568415077045876 747 1613204869675125 748 1659244529429568 749 1706568132565081 750 1755210675332505 751 1805208085218467 752 1856597234953902 753 1909415990531857 754 1963703223814344 755 2019498828010754 756 2076843768563626 757 2135780097305478 758 2196350969528687 759 2258600697861416 760 2322574768071683 761 2388319857914261 762 2455883894249936 763 2525316070638230 764 2596666868048394 765 2669988115388704 766 2745333009094789 767 2822756135929617 768 2902313537135152 769 2984062730123161 770 3068062733497329 771 3154374135114222 772 3243059116124553 773 3334181478399700 774 3427806716685045 775 3524002045146947 776 3622836427459782 777 3724380653388676 778 3828707368048789 779 3935891104800692 780 4046008366504197 781 4159137657776799 782 4275359521002068 783 4394756622554482 784 4517413788231823 785 4643418042584456 786 4772858700494787 787 4905827406125831 788 5042418175836555 789 5182727495387931 790 5326854362648027 791 5474900334448690 792 5626969629867535 793 5783169176991848 794 5943608663953443 795 6108400648635431 796 6277660609890327 797 6451507003174934 798 6630061377099462 799 6813448429376864 800 7001796067371141 801 7195235532009957 802 7393901458934928 803 7597931944348519 804 7807468676690346 805 8022657003351138 806 8243646002310114 807 8470588622180721 808 8703641754927180 809 8942966313659052 810 9188727381543427 811 9441094291077324 812 9700240708620529 813 9966344792758469 814 10239589280553035 815 10520161579283049 816 10808253934965589 817 11104063526234202 818 11407792563844631 819 11719648469935254 820 12039843980069119 821 12368597251190396 822 12706132052446016 823 13052677876023745 824 13408470054110377 825 13773749961986283 826 14148765138429964 827 14533769412482724 828 14929023119631202 829 15334793232414290 830 15751353497683603 831 16178984666840018 832 16617974637544941 833 17068618602276667 834 17531219293455816 835 18006087137045990 836 18493540413363510 837 18993905518211526 838 19507517129274049 839 20034718380000060 840 20575861137754880 841 21131306184082007 842 21701423402777842 843 22286592076202276 844 22887201080345897 845 23503649088095856 846 24136344885032931 847 24785707580557332 848 25452166827488264 849 26136163158539813 850 26838148214644669 851 27558584982224025 852 28297948151872929 853 29056724365173952 854 29835412470838002 855 30634523907023723 856 31454582968140941 857 32296127081416788 858 33159707214443844 859 34045888163337391 860 34955248851173541 861 35888382762590911 862 36845898255044183 863 37828418880737109 864 38836583849975681 865 39871048367156190 866 40932483978058430 867 42021579064052683 868 43139039204656285 869 44285587551925205 870 45461965357522121 871 46668932363936551 872 47907267208137887 873 49177767983728091 874 50481252662799194 875 51818559530917850 876 53190547786876397 877 54598097997610644 878 56042112566818443 879 57523516374711116 880 59043257268329963 881 60602306566405593 882 62201659742001432 883 63842336950821518 884 65525383574806606 885 67251870950490708 886 69022896938224666 887 70839586507517476 888 72703092514211255 889 74614596313444814 890 76575308389687296 891 78586469186197864 892 80649349765104814 893 82765252485379139 894 84935511887963861 895 87161495406293236 896 89444604095844125 897 91786273578915099 898 94187974809239722 899 96651214856677154 900 99177537915595545 901 101768526127652889 902 104425800425818877 903 107151021610685379 904 109945891235434917 905 112812152513364645 906 115751591466913683 907 118766037879511841 908 121857366271174565 909 125027497125004839 910 128278397910622421 911 131612084132896730 912 135030620641411008 913 138536122730606874 914 142130757266707220 915 145816744085665335 916 149596357175705010 917 153471925888260437 918 157445836430424625 919 161520533135569799 920 165698519764190799 921 169982361097465547 922 174374684302477399 923 178878180329371818 924 183495605612692523 925 188229783537819319 926 193083605941492486 927 198060034928493023 928 203162104446489846 929 208392921897056329 930 213755670075404930 931 219253608861540948 932 224890076949867356 933 230668493920323758 934 236592362053860569 935 242665268188896879 936 248890885932994915 937 255272977611710691 938 261815396260872334 939 268522087988090671 940 275397094064261753 941 282444553061470786 942 289668703374780480 943 297073885466429145 944 304664544159378350 945 312445231330103058 946 320420608316456416 947 328595448378091582 948 336974639571841883 949 345563187334488609 950 354366217121624467 951 363388977478231229 952 372636842808910923 953 382115316207693691 954 391830032736765274 955 401786762397126098 956 411991413162955620 957 422450034482879347 958 433168820465056952 959 444154113130120759 960 455412406149877369 961 466950348262033434 962 478774746757277010 963 490892571471457394 964 503310958445654403 965 516037213663543996 966 529078817314449032 967 542443427716138573 968 556138885319875095 969 570173217262329658 970 584554641569178539 971 599291571446684578 972 614392620142314902 973 629866605448589139 974 645722554300751223 975 661969707966723346 976 678617526872269388 977 695675695526295189 978 713154128062323840 979 731062973406854490 980 749412620554747512 981 768213704486186638 982 787477111702275515 983 807213985874652880 984 827435734162880902 985 848154033142375388 986 869380834854341121 987 891128373550894483 988 913409172042301941 989 936236048174422477 990 959622122030110576 991 983580822724871513 992 1008125895341566136 993 1033271408618721210 994 1059031762224993735 995 1085421694182287707 996 1112456289073967673 997 1140150985831320834 998 1168521585678522626 999 1197584260895232930 1000 1227355563149845674