0 1 1 1 2 2 3 3 4 6 5 8 6 11 7 18 8 24 9 30 10 45 11 57 12 71 13 96 14 120 15 148 16 192 17 235 18 286 19 354 20 431 21 518 22 628 23 752 24 893 25 1063 26 1262 27 1482 28 1744 29 2046 30 2386 31 2775 32 3231 33 3733 34 4305 35 4977 36 5715 37 6536 38 7507 39 8559 40 9735 41 11112 42 12608 43 14252 44 16177 45 18265 46 20553 47 23204 48 26090 49 29223 50 32848 51 36781 52 41049 53 45932 54 51243 55 56988 56 63528 57 70624 58 78301 59 86961 60 96382 61 106538 62 117941 63 130322 64 143669 65 158558 66 174739 67 192135 68 211459 69 232425 70 254984 71 279889 72 306923 73 335946 74 367863 75 402477 76 439642 77 480312 78 524418 79 571687 80 623270 81 679133 82 738995 83 804054 84 874487 85 949871 86 1031589 87 1119939 88 1214475 89 1316604 90 1426985 91 1544957 92 1672125 93 1809379 94 1956015 95 2113671 96 2283718 97 2465197 98 2659968 99 2869747 100 3093564 101 3333246 102 3591184 103 3866111 104 4160075 105 4476039 106 4812670 107 5171950 108 5557785 109 5968461 110 6406245 111 6875803 112 7375355 113 7907060 114 8476816 115 9082481 116 9726453 117 10415669 118 11147966 119 11925552 120 12757033 121 13639807 122 14576315 123 15576560 124 16637941 125 17762726 126 18962988 127 20235662 128 21583292 129 23019728 130 24542079 131 26152593 132 27867707 133 29684133 134 31604355 135 33647187 136 35809622 137 38093727 138 40521590 139 43089858 140 45800972 141 48679902 142 51723792 143 54934640 144 58341349 145 61941033 146 65736060 147 69758845 148 74007412 149 78483563 150 83224628 151 88228831 152 93498369 153 99074934 154 104958094 155 111149583 156 117696928 157 124600294 158 131862003 159 139534762 160 147620958 161 156122382 162 165098595 163 174553340 164 184489100 165 194971799 166 206008308 167 217600544 168 229822667 169 242683713 170 256186781 171 270413490 172 285377152 173 301080552 174 317614894 175 334997122 176 353231544 177 372418019 178 392579561 179 413720301 180 435951552 181 459301555 182 483776414 183 509497717 184 536501794 185 564795286 186 594512987 187 625698454 188 658361294 189 692648136 190 728613601 191 766268465 192 805774489 193 847196398 194 890548924 195 936007936 196 983652548 197 1033499434 198 1085742213 199 1140473401 200 1197715456 201 1257678280 202 1320472794 203 1386124978 204 1454865054 205 1526822074 206 1602029743 207 1680736852 208 1763096329 209 1849147111 210 1939161881 211 2033317007 212 2131661512 213 2234489872 214 2342008485 215 2454274629 216 2571610291 217 2694251582 218 2822269554 219 2956011263 220 3095751104 221 3241571701 222 3393851531 223 3552903063 224 3718826826 225 3892030970 226 4072875656 227 4261476998 228 4458279860 229 4663691997 230 4877853582 231 5101243983 232 5334329508 233 5577271957 234 5830593017 235 6094818935 236 6370142665 237 6657125692 238 6956366734 239 7268087297 240 7592898844 241 7931474193 242 8284074293 243 8651357701 244 9034085577 245 9432557250 246 9847489617 247 10279734274 248 10729641469 249 11197983060 250 11685718977 251 12193249472 252 12721413985 253 13271283389 254 13843322216 255 14438435643 256 15057825707 257 15702020650 258 16372005586 259 17069116880 260 17793964792 261 18547612451 262 19331553464 263 20146480034 264 20993549073 265 21874417559 266 22789880678 267 23741187154 268 24730183382 269 25757767884 270 26825301246 271 27934826661 272 29087370191 273 30284402451 274 31528192646 275 32819898033 276 34161122112 277 35554368799 278 37000954459 279 38502613551 280 40062120467 281 41680955875 282 43361011132 283 45105341553 284 46915623733 285 48793907197 286 50743568950 287 52766488563 288 54864903218 289 57042523666 290 59301471743 291 61644174840 292 64074723494 293 66595491313 294 69209128935 295 71920124213 296 74731148085 297 77645078358 298 80666852281 299 83799449843 300 87046017171 301 90411962059 302 93900625841 303 97515428807 304 101262307588 305 105144983349 306 109167198203 307 113335442449 308 117653877429 309 122126574385 310 126760647094 311 131560720712 312 136531250066 313 141680001698 314 147012133145 315 152532497043 316 158249592395 317 164169138284 318 170296447745 319 176640785636 320 183208515564 321 190005430302 322 197041650624 323 204324220622 324 211859483585 325 219658460043 326 227728970714 327 236077933934 328 244717372106 329 253655925263 330 262901172852 331 272466191658 332 282360551361 333 292592523510 334 303176353527 335 314122597657 336 325440319867 337 337144995362 338 349248293971 339 361760109358 340 374697281098 341 388072662423 342 401897092045 343 416188845584 344 430962103765 345 446228702558 346 462008507666 347 478317110594 348 495167477582 349 512581146420 350 530575290607 351 549164072485 352 568370876263 353 588214557135 354 608710624532 355 629884411162 356 651756652257 357 674344284381 358 697674786485 359 721770890298 360 746651140103 361 772345282095 362 798878271511 363 826270357898 364 854553776450 365 883755850924 366 913898746596 367 945017328273 368 977141548437 369 1010295603339 370 1044517246231 371 1079839232267 372 1116288030514 373 1153904446747 374 1192724333751 375 1232776579913 376 1274105340051 377 1316749769095 378 1360741453514 379 1406128084797 380 1452952465686 381 1501249059402 382 1551069429888 383 1602460268212 384 1655459231869 385 1710121983947 386 1766499502669 387 1824632852363 388 1884582176852 389 1946403019224 390 2010140225057 391 2075858686092 392 2143618965612 393 2213469943370 394 2285481688256 395 2359720117908 396 2436238580843 397 2515112632483 398 2596414065433 399 2680200992420 400 2766554952425 401 2855554007591 402 2947261533446 403 3041765411629 404 3139150563100 405 3239485986261 406 3342866474835 407 3449384267073 408 3559114557469 409 3672159462832 410 3788619221420 411 3908575653505 412 4032138845076 413 4159417567462 414 4290500919147 415 4425507442738 416 4564555227220 417 4707741152565 418 4855192952704 419 5007038646201 420 5163383655334 421 5324365475424 422 5490122947936 423 5660770627643 424 5836456599333 425 6017331248161 426 6203519141011 427 6395179609854 428 6592475601259 429 6795542377500 430 7004551471550 431 7219679231940 432 7441072622550 433 7668916137972 434 7903400678948 435 8144685722457 436 8392969816680 437 8648459383441 438 8911327564677 439 9181787832003 440 9460063450675 441 9746342181548 442 10040853658755 443 10343839108159 444 10655502218547 445 10976089804222 446 11305862564574 447 11645041222978 448 11993891182598 449 12352693891782 450 12721688621208 451 13101160545462 452 13491413578958 453 13892706823196 454 14305346814960 455 14729661416239 456 15165931298792 457 15614485720973 458 16075678442627 459 16549813180278 460 17037243737809 461 17538351485499 462 18053465167923 463 18582964698596 464 19127261259269 465 19686710345088 466 20261720063000 467 20852733367515 468 21460134766676 469 22084362346075 470 22725893346726 471 23385143291645 472 24062582608885 473 24758725071580 474 25474019782320 475 26208971581014 476 26964133637000 477 27739990936062 478 28537085414457 479 29356012190842 480 30197295074769 481 31061515488527 482 31949313742734 483 32861255120283 484 33797963561048 485 34760127504420 486 35748357070598 487 36763321452615 488 37805760890573 489 38876333368525 490 39975756793884 491 41104826576821 492 42264252387908 493 43454803982244 494 44677336076255 495 45932613521187 496 47221461865382 497 48544798969931 498 49903449210107 499 51298297494320 500 52730329528231 501 54200433234258 502 55709557351244 503 57258759801806 504 58848996966256 505 60481285515565 506 62156760923944 507 63876452628675 508 65641450299632 509 67452971915430 510 69312125567005 511 71220078631708 512 73178137615836 513 75187494518913 514 77249400143497 515 79365255177973 516 81536341901092 517 83763999910680 518 86049730878570 519 88394913334446 520 90800982173529 521 93269546499678 522 95802088306308 523 98400143909635 524 101065437494558 525 103799561352629 526 106604160609661 527 109481081845852 528 112432035816392 529 115458783404702 530 118563302240867 531 121747429356093 532 125013049747125 533 128362280387204 534 131797093791353 535 135319507007774 536 138931786140496 537 142636048069185 538 146434451344053 539 150329420563299 540 154323227410000 541 158418180999175 542 162616875446894 543 166921747328933 544 171335266974309 545 175860208646781 546 180499185643173 547 185254839800425 548 190130137945102 549 195127881510927 550 200250895904586 551 205502352577271 552 210885254447582 553 216402622180523 554 222057845787710 555 227854142650238 556 233794742351979 557 239883267092187 558 246123163772433 559 252517884116856 560 259071298222709 561 265787097255749 562 272668970492939 563 279721051320610 564 286947292101290 565 294351634686268 566 301938493462290 567 309712098668492 568 317676662116245 569 325836896518429 570 334197329102591 571 342762458701088 572 351537316253072 573 360526744834850 574 369735549852684 575 379169100047533 576 388832575913054 577 398731108732265 578 408870427401253 579 419256071088187 580 429893519020767 581 440788882366404 582 451948083228361 583 463376970609222 584 475082062991554 585 487069689445355 586 499346093655011 587 511918226322270 588 524792850762241 589 537976629952923 590 551476974958001 591 565301110500915 592 579456146878032 593 593949983545474 594 608790337229634 595 623984793373123 596 639541771454575 597 655469510807089 598 671776103544004 599 688470520630818 600 705561558406225 601 723057847116682 602 740968944670161 603 759304238870395 604 778072933472709 605 797285208735986 606 816951082604544 607 837080367805796 608 857683906681902 609 878772386020180 610 900356267307876 611 922447094822411 612 945056267566884 613 968194935739133 614 991875389980368 615 1016109785066500 616 1040910004660475 617 1066289130502877 618 1092260121762724 619 1118835640465480 620 1146029609229965 621 1173855840635391 622 1202327825290078 623 1231460376885701 624 1261268215800951 625 1291765711776785 626 1322968625365625 627 1354892639766353 628 1387553060183237 629 1420966650229478 630 1455150116867009 631 1490119757675428 632 1525893401721078 633 1562488841455271 634 1599923429889823 635 1638216124570086 636 1677385871729662 637 1717451143734455 638 1758432096361880 639 1800348898736679 640 1843221213270816 641 1887070464662763 642 1931918121300159 643 1977785107397991 644 2024694194419926 645 2072668227489474 646 2121729471885350 647 2171902124959937 648 2223210493938693 649 2275678265556201 650 2329331150043435 651 2384195003577782 652 2440295023043279 653 2497658520074535 654 2556312995060505 655 2616285245200187 656 2677604280761563 657 2740299343515250 658 2804398930179376 659 2869933848525436 660 2936935188118339 661 3005433246324521 662 3075460736908907 663 3147050705887379 664 3220235362053439 665 3295049435702004 666 3371528048180500 667 3449705432921947 668 3529618457762047 669 3611304440676825 670 3694799763553100 671 3780143555362835 672 3867375463301756 673 3956534144378075 674 4047661123481719 675 4140798512543814 676 4235987382085358 677 4333271790884893 678 4432696463426508 679 4534305025235158 680 4638144219220474 681 4744261533824579 682 4852703304019284 683 4963519110790203 684 5076759371098248 685 5192473287513834 686 5310713446600668 687 5431533362727743 688 5554985278341038 689 5681124957108047 690 5810009194118430 691 5941693448464816 692 6076236847408544 693 6213699655054332 694 6354140739045581 695 6497622781468695 696 6644209719659647 697 6793964027091680 698 6946952148224514 699 7103241903269162 700 7262899585401812 701 7425995614670413 702 7592601921364990 703 7762788838413879 704 7936630992154335 705 8114204656468369 706 8295584442401546 707 8480849419990264 708 8670080459373914 709 8863356694834649 710 9060761896669011 711 9262381791369719 712 9468300301775317 713 9678606162673693 714 9893390237561162 715 10112741510960504 716 10336753967500305 717 10565523897019657 718 10799145640905700 719 11037718727360911 720 11281345184406569 721 11530125014615598 722 11784163606772947 723 12043569048796907 724 12308447332469462 725 12578910033784115 726 12855071647057352 727 13137044491940405 728 13424946683672419 729 13718899480272937 730 14019021893867240 731 14325438942154138 732 14638279031451304 733 14957668243034880 734 15283738887599244 735 15616626916664640 736 15956465885912550 737 16303395802497454 738 16657560589837147 739 17019101696504434 740 17388167259456525 741 17764909614886755 742 18149478554216029 743 18542030792176446 744 18942727550676033 745 19351727428962615 746 19769196200397806 747 20195304461817831 748 20630220119658597 749 21074118502800195 750 21527180107266208 751 21989582663277491 752 22461511588311078 753 22943157820169806 754 23434709466504346 755 23936362584593440 756 24448319135152073 757 24970778176618325 758 25503946996811699 759 26048039180581368 760 26603265351001998 761 27169844637874928 762 27748002893781241 763 28337962942470208 764 28939956409782536 765 29554222082236537 766 30180995664812203 767 30820521957033119 768 31473053391833152 769 32138839260323556 770 32818138259907694 771 33511217208091212 772 34218339735962501 773 34939779189494062 774 35675817558826338 775 36426733596197576 776 37192816097991026 777 37974363044149662 778 38771669142714175 779 39585039471378088 780 40414788871544156 781 41261228872647063 782 42124681720798433 783 43005480023099899 784 43903953053720280 785 44820441146829001 786 45755295639287943 787 46708864508317511 788 47681507157191637 789 48673594652303913 790 49685494695292706 791 50717586776315426 792 51770262756745124 793 52843911123122382 794 53938932536596134 795 55055740758812991 796 56194746190893524 797 57356371790509609 798 58541054396599925 799 59749227497447755 800 60981337545163943 801 62237845677809203 802 63519209719358284 803 64825900860529573 804 66158405837834720 805 67517208107268245 806 68902804921728198 807 70315709965846290 808 71756433706932775 809 73225500834350144 810 74723453415042199 811 76250830360561275 812 77808185258145416 813 79396090047306354 814 81015113606490139 815 82665839938614653 816 84348872438652100 817 86064811534710573 818 87814273258367856 819 89597894104378813 820 91416307731137220 821 93270163875006251 822 95160133876400177 823 97086886371500712 824 99051106580535229 825 101053502503598116 826 103094779609382719 827 105175660451719580 828 107296891615284921 829 109459217329305355 830 111663399443191600 831 113910225127170503 832 116200479416535740 833 118534965496783554 834 120914513244621008 835 123339950628147228 836 125812124332380243 837 128331909146300391 838 130900178225864083 839 133517824005095481 840 136185768521756629 841 138904932465197770 842 141676256402621572 843 144500712051191239 844 147379270118086576 845 150312921783059592 846 153302691016346539 847 156349601128178266 848 159454696537290106 849 162619056143704096 850 165843758597259317 851 169129904288019686 852 172478629879098156 853 175891072208156183 854 179368390528180409 855 182911782212464110 856 186522445300269980 857 190201600916909626 858 193950510263823375 859 197770435717894050 860 201662663459626174 861 205628521762874087 862 209669340659342022 863 213786474697998649 864 217981322654412374 865 222255285667139610 866 226609790156586306 867 231046308969496765 868 235566318001024461 869 240171319188728864 870 244862863221437061 871 249642504550081083 872 254511824482618636 873 259472455475729058 874 264526034549480401 875 269674226392777908 876 274918749376057889 877 280261327267487954 878 285703712373914613 879 291247713294808616 880 296895144958526264 881 302647851700994024 882 308507736906632169 883 314476711258882885 884 320556715779251340 885 326749753379383641 886 333057835347355882 887 339483004239521092 888 346027367499447837 889 352693042069298482 890 359482177156572084 891 366396989947383386 892 373439708365701666 893 380612593599097053 894 387917978071149864 895 395358206235099274 896 402935656879122706 897 410652783386718205 898 418512052591277114 899 426515966734589936 900 434667106191755863 901 442968066269692438 902 451421478835379174 903 460030057537807243 904 468796532579583481 905 477723671879812444 906 486814328981121121 907 496071375671566333 908 505497722696627092 909 515096370386094184 910 524870339160793591 911 534822689648377053 912 544956576227705359 913 555275175294167096 914 565781704789793433 915 576479480704766456 916 587371843140860862 917 598462175097133462 918 609753962138732394 919 621250716127251767 920 632955993270708429 921 644873457003485675 922 657006799426021601 923 669359758448624979 924 681936184104130631 925 694739957563359251 926 707775007378594493 927 721045379274330089 928 734555152786926542 929 748308456423093265 930 762309541164891659 931 776562694597009989 932 791072254979969648 933 805842688519097273 934 820878501032610375 935 836184250742567451 936 851764629558401496 937 867624372143348409 938 883768267419112995 939 900201243916297801 940 916928276300532889 941 933954395379964077 942 951284777785005141 943 968924649808861629 944 986879295907742816 945 1005154152767864166 946 1023754710529837762 947 1042686519552640522 948 1061955289145628214 949 1081566786026876423 950 1101526839337301792 951 1121841444100575977 952 1142516656990280752 953 1163558599349252565 954 1184973565669078859 955 1206767916514787091 956 1228948079531190629 957 1251520663006304182 958 1274492346037742215 959 1297869877262083998 960 1321660193811581497 961 1345870308569209124 962 1370507306594002440 963 1395578469540117822 964 1421091160092738635 965 1447052815808554014 966 1473471079324169829 967 1500353679814452116 968 1527708424215148225 969 1555543333292243344 970 1583866520227178736 971 1612686178922283621 972 1642010726272197464 973 1671848677715978494 974 1702208632583633340 975 1733099422647193444 976 1764529984756707012 977 1796509342904683063 978 1829046763416240125 979 1862151624505475859 980 1895833395010388112 981 1930101796305108408 982 1964966668902808680 983 2000437947516554523 984 2036525830069539531 985 2073240641181570528 986 2110592803501624542 987 2148593013899810656 988 2187252103977695272 989 2226581007302975414 990 2266590943179906993 991 2307293274021004705 992 2348699468417483650 993 2390821292576394167 994 2433670664706693354 995 2477259613533435160 996 2521600477819306012 997 2566705757598581453 998 2612588068060042567 999 2659260347242969258 1000 2706735704289906525