0 0 1 0 2 1 3 3 4 11 5 26 6 58 7 110 8 199 9 331 10 532 11 811 12 1206 13 1729 14 2432 15 3331 16 4494 17 5942 18 7760 19 9975 20 12692 21 15944 22 19858 23 24473 24 29941 25 36308 26 43752 27 52327 28 62239 29 73551 30 86499 31 101155 32 117788 33 136479 34 157532 35 181038 36 207338 37 236534 38 269005 39 304865 40 344534 41 388138 42 436140 43 488678 44 546261 45 609040 46 677571 47 752019 48 832989 49 920661 50 1015691 51 1118274 52 1229120 53 1348439 54 1476997 55 1615020 56 1763332 57 1922176 58 2092435 59 2274370 60 2468926 61 2676382 62 2897747 63 3133318 64 3384171 65 3650622 66 3933815 67 4234086 68 4552649 69 4889861 70 5247008 71 5624468 72 6023602 73 6444809 74 6889527 75 7358177 76 7852276 77 8372268 78 8919750 79 9495190 80 10100268 81 10735476 82 11402579 83 12102093 84 12835871 85 13604454 86 14409784 87 15252428 88 16134419 89 17056351 90 18020350 91 19027037 92 20078634 93 21175789 94 22320822 95 23514409 96 24758970 97 26055210 98 27405650 99 28811025 100 30273960 101 31795220 102 33377536 103 35021703 104 36730561 105 38504936 106 40347778 107 42259945 108 44244499 109 46302331 110 48436617 111 50648281 112 52940616 113 55314579 114 57773582 115 60318616 116 62953214 117 65678402 118 68497835 119 71412575 120 74426402 121 77540414 122 80758518 123 84081848 124 87514441 125 91057468 126 94715097 127 98488537 128 102382089 129 106397001 130 110537709 131 114805500 132 119204948 133 123737379 134 128407507 135 133216698 136 138169808 137 143268244 138 148517005 139 153917540 140 159474994 141 165190858 142 171070425 143 177115228 144 183330711 145 189718450 146 196284041 147 203029104 148 209959389 149 217076561 150 224386526 151 231890994 152 239596030 153 247503389 154 255619297 155 263945555 156 272488552 157 281250136 158 290236860 159 299450620 160 308898136 161 318581352 162 328507157 163 338677543 164 349099571 165 359775282 166 370711910 167 381911546 168 393381599 169 405124211 170 417146968 171 429452063 172 442047262 173 454934809 174 468122652 175 481613087 176 495414246 177 509528478 178 523964100 179 538723515 180 553815228 181 569241696 182 585011614 183 601127493 184 617598221 185 634426364 186 651621004 187 669184763 188 687126919 189 705450151 190 724163935 191 743271007 192 762781044 193 782696839 194 803028272 195 823778194 196 844956690 197 866566670 198 888618425 199 911114925 200 934066670 201 957476690 202 981355696 203 1005706778 204 1030540861 205 1055861096 206 1081678623 207 1107996655 208 1134826549 209 1162171581 210 1190043327 211 1218445126 212 1247388776 213 1276877679 214 1306923857 215 1337530776 216 1368710684 217 1400467112 218 1432812535 219 1465750550 220 1499293862 221 1533446134 222 1568220303 223 1603620098 224 1639658691 225 1676339878 226 1713677067 227 1751674122 228 1790344689 229 1829692701 230 1869732044 231 1910466720 232 1951910858 233 1994068529 234 2036954107 235 2080571733 236 2124936028 237 2170051204 238 2215932130 239 2262583090 240 2310019204 241 2358244828 242 2407275335 243 2457115153 244 2507779911 245 2559274110 246 2611613636 247 2664803064 248 2718858539 249 2773784711 250 2829597986 251 2886303089 252 2943916690 253 3002443589 254 3061900722 255 3122292965 256 3183637522 257 3245939346 258 3309215910 259 3373472245 260 3438726096 261 3504982572 262 3572259692 263 3640562643 264 3709909721 265 3780306192 266 3851770630 267 3924308381 268 3997938299 269 4072665811 270 4148510053 271 4225476533 272 4303584672 273 4382840059 274 4463262402 275 4544857372 276 4627644966 277 4711630938 278 4796835575 279 4883264715 280 4970938938 281 5059864166 282 5150061274 283 5241536268 284 5334310321 285 5428389524 286 5523795349 287 5620533973 288 5718627169 289 5818081201 290 5918918145 291 6021144352 292 6124782204 293 6229838139 294 6336334847 295 6444278854 296 6553693160 297 6664584380 298 6776975825 299 6890874200 300 7006303130 301 7123269410 302 7241796981 303 7361892728 304 7483580911 305 7606868506 306 7731780093 307 7858322740 308 7986521349 309 8116383081 310 8247933162 311 8381178846 312 8516145686 313 8652841029 314 8791290757 315 8931502311 316 9073501904 317 9217297072 318 9362914360 319 9510361400 320 9659665072 321 9810833104 322 9963892713 323 10118851723 324 10275737691 325 10434558538 326 10595342162 327 10758096582 328 10922850039 329 11089610651 330 11258407004 331 11429247315 332 11602160518 333 11777154929 334 11954259832 335 12133483643 336 12314855998 337 12498385414 338 12684101880 339 12872014015 340 13062152164 341 13254525048 342 13449163370 343 13646075953 344 13845293861 345 14046826020 346 14250703856 347 14456936399 348 14665555439 349 14876570111 350 15090012571 351 15305892059 352 15524241100 353 15745069039 354 15968408772 355 16194269750 356 16422685242 357 16653664806 358 16887242085 359 17123426745 360 17362252806 361 17603730042 362 17847892852 363 18094751118 364 18344339621 365 18596668352 366 18851772475 367 19109662091 368 19370372749 369 19633914661 370 19900323763 371 20169610378 372 20441810832 373 20716935559 374 20995021277 375 21276078532 376 21560144436 377 21847229648 378 22137371675 379 22430581290 380 22726896398 381 23026327886 382 23328914059 383 23634665918 384 23943622171 385 24255793934 386 24571220319 387 24889912558 388 25211910169 389 25537224501 390 25865895480 391 26197934572 392 26533382114 393 26872249689 394 27214578047 395 27560378889 396 27909693380 397 28262533340 398 28618940350 399 28978926350 400 29342533340 401 29709773380 402 30080688891 403 30455292053 404 30833625711 405 31215702166 406 31601564688 407 31991225700 408 32384728899 409 32782086831 410 33183343622 411 33588511941 412 33997636346 413 34410729629 414 34827836782 415 35248970721 416 35674176874 417 36103468282 418 36536890810 419 36974457625 420 37416215032 421 37862176324 422 38312388248 423 38766864223 424 39225651441 425 39688763448 426 40156247882 427 40628118417 428 41104423139 429 41585175851 430 42070425089 431 42560184785 432 43054503928 433 43553396579 434 44056912182 435 44565064928 436 45077904718 437 45595445874 438 46117738755 439 46644797815 440 47176673874 441 47713381518 442 48254972030 443 48801460128 444 49352897561 445 49909299180 446 50470717201 447 51037166609 448 51608700089 449 52185332761 450 52767117781 451 53354070404 452 53946244260 453 54543654739 454 55146355947 455 55754363410 456 56367731712 457 56986476516 458 57610652885 459 58240276620 460 58875403266 461 59516048762 462 60162269137 463 60814080468 464 61471539271 465 62134661762 466 62803504945 467 63478085176 468 64158459949 469 64844645761 470 65536700598 471 66234641098 472 66938525742 473 67648371309 474 68364236777 475 69086139067 476 69814137656 477 70548249608 478 71288534900 479 72035010740 480 72787737608 481 73546732856 482 74312057469 483 75083728943 484 75861808771 485 76646314594 486 77437308414 487 78234808018 488 79038875919 489 79849530051 490 80666833440 491 81490804167 492 82321505774 493 83158956489 494 84003220372 495 84854315799 496 85712307350 497 86577213550 498 87449099500 499 88327983875 500 89213932300 501 90106963600 502 91007143926 503 91914492253 504 92829075261 505 93750912076 506 94680069908 507 95616568035 508 96560474199 509 97511807831 510 98470637207 511 99436981911 512 100410910756 513 101392443479 514 102381649432 515 103378548506 516 104383210594 517 105395655742 518 106415954385 519 107444126725 520 108480243742 521 109524325794 522 110576444408 523 111636620098 524 112704924941 525 113781379608 526 114866056727 527 115958977127 528 117060213989 529 118169788301 530 119287773799 531 120414191630 532 121549116088 533 122692568479 534 123844623657 535 125005303088 536 126174682188 537 127352782584 538 128539680255 539 129735396990 540 130940009334 541 132153539238 542 133376063815 543 134607605178 544 135848241011 545 137097993590 546 138356941171 547 139625106194 548 140902567489 549 142189347661 550 143485526116 551 144791125624 552 146106226170 553 147430850689 554 148765079747 555 150108936445 556 151462501932 557 152825799476 558 154198910810 559 155581859370 560 156974727476 561 158377538732 562 159790376047 563 161213263193 564 162646283671 565 164089461422 566 165542880540 567 167006565136 568 168480599899 569 169965009111 570 171459878058 571 172965231193 572 174481154402 573 176007672309 574 177544871402 575 179092776477 576 180651474626 577 182220990818 578 183801412750 579 185392765565 580 186995137568 581 188608554076 582 190233104004 583 191868812843 584 193515770121 585 195174001504 586 196843597134 587 198524582853 588 200217049419 589 201921022851 590 203636594525 591 205363790637 592 207102703184 593 208853358539 594 210615849322 595 212390202084 596 214176510070 597 215974800010 598 217785165775 599 219607634275 600 221442300010 601 223289190070 602 225148399586 603 227019955828 604 228903954561 605 230800423236 606 232709458253 607 234631087245 608 236565407249 609 238512446081 610 240472301417 611 242445001256 612 244430643916 613 246429257579 614 248440941207 615 250465723166 616 252503703064 617 254554909452 618 256619442585 619 258697331200 620 260788676202 621 262893506514 622 265011923693 623 267143956848 624 269289708191 625 271449207018 626 273622556197 627 275809785212 628 278010997589 629 280226223001 630 282455565634 631 284699055350 632 286956796998 633 289228820629 634 291515231757 635 293816060623 636 296131413408 637 298461320544 638 300805888880 639 303165149040 640 305539208544 641 307928098208 642 310331926225 643 312750723603 644 315184599211 645 317633584250 646 320097788266 647 322577242654 648 325072057639 649 327582264811 650 330107975076 651 332649220219 652 335206111830 653 337778681889 654 340367042672 655 342971226355 656 345591345902 657 348227433686 658 350879603360 659 353547887495 660 356232400436 661 358933174952 662 361650326082 663 364383886793 664 367133972821 665 369900617332 666 372683936760 667 375483964471 668 378300817599 669 381134529711 670 383985218643 671 386852918163 672 389737746812 673 392639738559 674 395559012652 675 398495603262 676 401449630346 677 404421128278 678 407410217725 679 410416933265 680 413441396278 681 416483641546 682 419543791164 683 422621880118 684 425718031221 685 428832279664 686 431964748979 687 435115474563 688 438284580669 689 441472102901 690 444678166235 691 447902806482 692 451146149344 693 454408230839 694 457689177397 695 460989025244 696 464307901540 697 467645842720 698 471002976675 699 474379340050 700 477775061470 701 481190177790 702 484624818371 703 488079020278 704 491552913611 705 495046535646 706 498560017223 707 502093395830 708 505646803049 709 509220276581 710 512813948752 711 516427857476 712 520062135826 713 523716821929 714 527392049607 715 531087857201 716 534804379284 717 538541654412 718 542299817910 719 546078908550 720 549879062412 721 553700318484 722 557542813603 723 561406586973 724 565291776191 725 569198420678 726 573126658792 727 577076530172 728 581048173939 729 585041629951 730 589057038094 731 593094438445 732 597153971658 733 601235678029 734 605339698982 735 609466075033 736 613614948378 737 617786359754 738 621980452130 739 626197266465 740 630436946504 741 634699533428 742 638985171760 743 643293902903 744 647625872161 745 651981121160 746 656359795986 747 660761938489 748 665187695539 749 669637109211 750 674110327161 751 678607391689 752 683128451240 753 687673548339 754 692242832222 755 696836345640 756 701454238622 757 706096554146 758 710763443035 759 715454948495 760 720171222146 761 724912307422 762 729678356742 763 734469413768 764 739285631721 765 744127054492 766 748993836105 767 753886020681 768 758803763049 769 763747107561 770 768716209853 771 773711114508 772 778731977972 773 783778845059 774 788851873027 775 793951106922 776 799076704816 777 804228711988 778 809407287325 779 814612476340 780 819844438738 781 825103220266 782 830388981449 783 835701768268 784 841041742071 785 846408949074 786 851803551449 787 857225595648 788 862675244669 789 868152545201 790 873657661070 791 879190639202 792 884751644254 793 890340723389 794 895958042097 795 901603647779 796 907277706760 797 912980266680 798 918711494700 799 924471438700 800 930260266680 801 936078026760 802 941924887781 803 947800898103 804 953706227411 805 959640924306 806 965605159318 807 971598981290 808 977622561599 809 983675949331 810 989759316712 811 995872713071 812 1002016311486 813 1008190161529 814 1014394437132 815 1020629188111 816 1026894589254 817 1033190690622 818 1039517667860 819 1045875571275 820 1052264577372 821 1058684736704 822 1065136226638 823 1071619097973 824 1078133528941 825 1084679570588 826 1091257402012 827 1097867074507 828 1104508768039 829 1111182534151 830 1117888553679 831 1124626878415 832 1131397690068 833 1138201040679 834 1145037112832 835 1151905958818 836 1158807762098 837 1165742575214 838 1172710582505 839 1179711836765 840 1186746523214 841 1193814694898 842 1200916537920 843 1208052105578 844 1215221584861 845 1222425029320 846 1229662626831 847 1236934431199 848 1244240631189 849 1251581280861 850 1258956569871 851 1266366552534 852 1273811419400 853 1281291225039 854 1288806160897 855 1296356281800 856 1303941780092 857 1311562710856 858 1319219267335 859 1326911504870 860 1334639617606 861 1342403661142 862 1350203830527 863 1358040181618 864 1365912910371 865 1373822072902 866 1381767866075 867 1389750346266 868 1397769711249 869 1405826017661 870 1413919464188 871 1422050107728 872 1430218147882 873 1438423641809 874 1446666790027 875 1454947649957 876 1463266423036 877 1471623166948 878 1480018084050 879 1488451232290 880 1496922814948 881 1505432890236 882 1513981662359 883 1522569189793 884 1531195677671 885 1539861184734 886 1548565917044 887 1557309933608 888 1566093441419 889 1574916499751 890 1583779316530 891 1592681951297 892 1601624612914 893 1610607361189 894 1619630405922 895 1628693807189 896 1637797775730 897 1646942371890 898 1656127807350 899 1665354142725 900 1674621590640 901 1683930211980 902 1693280220316 903 1702671676803 904 1712104795961 905 1721579639216 906 1731096422038 907 1740655206125 908 1750256207899 909 1759899489331 910 1769585267797 911 1779313605541 912 1789084720896 913 1798898676379 914 1808755691282 915 1818655828396 916 1828599307974 917 1838586193082 918 1848616704935 919 1858690906875 920 1868809021082 921 1878971111174 922 1889177400298 923 1899427952348 924 1909722991441 925 1920062581748 926 1930446948357 927 1940876155717 928 1951350429889 929 1961869835601 930 1972434599889 931 1983044787760 932 1993700627228 933 2004402183579 934 2015149685807 935 2025943199478 936 2036782954568 937 2047669016924 938 2058601617505 939 2069580822440 940 2080606863674 941 2091679807618 942 2102799887205 943 2113967169128 944 2125181887311 945 2136444108730 946 2147754068301 947 2159111833284 948 2170517639589 949 2181971554761 950 2193473815706 951 2205024490254 952 2216623816310 953 2228271861989 954 2239968866197 955 2251714897335 956 2263510195312 957 2275354828816 958 2287249038760 959 2299192894120 960 2311186636816 961 2323230336112 962 2335324234937 963 2347468402843 964 2359663083771 965 2371908347562 966 2384204439170 967 2396551428726 968 2408949562199 969 2421398910011 970 2433899719148 971 2446452060323 972 2459056181542 973 2471712153809 974 2484420226152 975 2497180469867 976 2509993135006 977 2522858293158 978 2535776195400 979 2548746913615 980 2561770699908 981 2574847626456 982 2587977946394 983 2601161732193 984 2614399238021 985 2627690536644 986 2641035883264 987 2654435350943 988 2667889195919 989 2681397491551 990 2694960495115 991 2708578280267 992 2722251105324 993 2735979044239 994 2749762356372 995 2763601115974 996 2777495583450 997 2791445833350 998 2805452127125 999 2819514539625 1000 2833633333350