0 1 1 2 2 3 3 4 4 7 5 8 6 9 7 14 8 20 9 20 10 21 11 32 12 43 13 46 14 51 15 62 16 71 17 82 18 107 19 136 20 145 21 136 22 144 23 200 24 280 25 316 26 296 27 294 28 359 29 456 30 535 31 576 32 591 33 650 34 820 35 1020 36 1078 37 990 38 963 39 1160 40 1541 41 1950 42 2225 43 2244 44 2034 45 1892 46 2211 47 3024 48 3866 49 4260 50 4207 51 4066 52 4150 53 4630 54 5617 55 6978 56 8103 57 8272 58 7513 59 6888 60 7627 61 9980 62 12983 63 15258 64 16073 65 15742 66 14995 67 14276 68 14193 69 16180 70 21335 71 28284 72 33375 73 33834 74 30436 75 26808 76 26494 77 30774 78 38494 79 47174 80 54476 81 59286 82 61484 83 60782 84 57044 85 52840 86 54372 87 67182 88 89927 89 113356 90 126439 91 124366 92 111943 93 99900 94 97062 95 105392 96 122486 97 147074 98 179174 99 214858 100 244028 101 255520 102 244634 103 217046 104 188128 105 178542 106 205539 107 271632 108 358347 109 433492 110 470463 111 465768 112 439626 113 417792 114 410823 115 412504 116 420560 117 454368 118 542328 119 687118 120 848244 121 964252 122 992376 123 930048 124 811476 125 695170 126 647741 127 717722 128 908262 129 1172480 130 1438751 131 1645624 132 1763479 133 1797044 134 1772665 135 1716300 136 1636769 137 1534510 138 1437507 139 1430650 140 1631860 141 2107000 142 2783446 143 3449176 144 3861868 145 3890588 146 3583074 147 3125618 148 2744743 149 2610092 150 2774771 151 3183356 152 3748919 153 4428410 154 5209279 155 6024874 156 6718973 157 7126116 158 7183246 159 6944064 160 6494318 161 5900100 162 5283874 163 4944454 164 5326937 165 6760254 166 9130388 167 11792156 168 13867728 169 14743870 170 14388698 171 13272918 172 12027237 173 11128032 174 10771516 175 10916046 176 11433178 177 12309842 178 13768630 179 16145488 180 19540315 181 23511316 182 27121143 183 29367680 184 29690383 185 28176856 186 25389640 187 22091650 188 19166350 189 17675190 190 18714571 191 22920478 192 29932685 193 38314612 194 46095880 195 51607370 196 54092036 197 53807780 198 51711051 199 48991164 200 46642657 201 45135830 202 44300348 203 43655576 204 43226608 205 44320132 206 49376441 207 60500094 208 77434839 209 96578768 210 112196007 211 119362812 212 116647950 213 106558236 214 93599567 215 81779924 216 73527996 217 70260832 218 73229361 219 83453314 220 100911948 221 123930854 222 149328643 223 173232404 224 192213570 225 204310976 226 209421947 227 208811330 228 204122492 229 196576986 230 186703745 231 174600406 232 160865584 233 148267144 234 143214705 235 155039618 236 191767006 237 253896536 238 330523521 239 401866118 240 448075531 241 459049020 242 438542153 243 400088598 244 358609665 245 324250222 246 301703507 247 292923772 248 299179623 249 320975456 250 357538721 251 407553180 252 470342321 253 545473386 254 630422803 255 718240376 256 797290665 257 853542068 258 874756295 259 855519710 260 800898657 261 725521160 262 647283919 263 580263098 264 533650033 265 518049224 266 551701099 267 656887004 268 844815409 269 1098857012 270 1370416549 271 1594487678 272 1718119571 273 1724923150 274 1640268480 275 1514532684 276 1396386982 277 1313310624 278 1268666466 279 1251565498 280 1249149584 281 1254821852 282 1273221026 283 1324023734 284 1441415492 285 1662918090 286 2007207436 287 2451701554 288 2925786486 289 3328394626 290 3564424578 291 3583210302 292 3399722052 293 3086229524 294 2737376546 295 2428860964 296 2196429266 297 2048253482 298 1997653432 299 2086340706 300 2375716088 301 2908430414 302 3664461460 303 4541253700 304 5375465699 305 6001915010 306 6322934387 307 6349955124 308 6189343329 309 5976564802 310 5798753580 311 5657392932 312 5495036820 313 5260842912 314 4961105054 315 4660505884 316 4449121126 317 4418944784 318 4671230692 319 5326786978 320 6492100220 321 8172867370 322 10189541190 323 12173202568 324 13675046328 325 14343302176 326 14071510868 327 13037288944 328 11614773270 329 10212481892 330 9123438062 331 8460376292 332 8194761826 333 8256817980 334 8625228562 335 9356226364 336 10548544436 337 12273685158 338 14505644791 339 17077809036 340 19692674029 341 22000278008 342 23724061377 343 24763208894 344 25192157064 345 25146859890 346 24690154087 347 23781822974 348 22387418464 349 20619462038 350 18763270776 351 17155658424 352 16045178324 353 15592851050 354 16025924876 355 17773322202 356 21377280622 357 27142952412 358 34724684906 359 42957121770 360 50122371370 361 54576025916 362 55421578484 363 52881515000 364 48180356916 365 43011424948 366 38853878918 367 36454468272 368 35691144290 369 35848844440 370 36143026288 371 36214670510 372 36353344802 373 37365797266 374 40196443961 375 45507221406 376 53394986008 377 63321298002 378 74240152057 379 84864598948 380 93980319781 381 100680858446 382 104423292367 383 104930123032 384 102108781693 385 96152341404 386 87772950809 387 78297011726 388 69387903552 389 62488804502 390 58396719556 391 57343874358 392 59549836512 393 65765513290 394 77255896620 395 95047992824 396 118823830998 397 146168954252 398 172768358932 399 193640369416 400 204911193602 401 205307057032 402 196658630794 403 183175066968 404 169779540178 405 160182208578 406 155511682388 407 154172436288 408 153078232954 409 149657731654 410 143497077860 411 136674606152 412 132740352745 413 135210452698 414 146595388441 415 168262019380 416 200576725479 417 242637661246 418 291575630237 419 342144059106 420 387333954579 421 420015790244 422 434861164154 423 429712824248 424 406080312500 425 368894295446 426 325639432510 427 284782978286 428 253587010531 429 236005059330 430 231804663818 431 237680142162 432 249995444166 433 267709303940 434 293765139200 435 333939049072 436 393415724610 437 472616220038 438 564487778338 439 655119488598 440 728045532528 441 770553357114 442 778949296148 443 760020288210 444 727779815748 445 696948867056 446 676286460000 447 665090794848 448 654756467028 449 634658427124 450 599108738528 451 551379163778 452 502651686677 453 467175194390 454 457326795290 455 481714579208 456 546342482198 457 655876875176 458 811923829066 459 1008243649838 460 1226438959973 461 1436564770894 462 1604226173641 463 1701237340606 464 1714435089001 465 1648647094690 466 1523660294740 467 1368025827004 468 1212614831292 469 1084894941842 470 1003553553387 471 973900212344 472 986349829555 473 1020664379198 474 1056128781172 475 1083764291826 476 1114083257956 477 1175094277460 478 1300068644648 479 1510315576082 480 1801480670118 481 2140625126052 482 2476097224784 483 2755809342244 484 2945447795252 485 3038402128922 486 3053351996708 487 3021194050506 488 2967765067174 489 2900855796580 490 2808402510860 491 2669486851002 492 2472600669438 493 2230449043748 494 1981580051089 495 1777099982274 496 1660889545785 497 1656499956838 498 1768973432868 499 1998337113068 500 2352141474694 501 2844615204688 502 3480009649651 503 4230217688236 504 5022591271481 505 5748841770256 506 6293564662453 507 6569666489830 508 6544875181062 509 6249631219520 510 5766716939113 511 5209713306052 512 4697363080558 513 4327262355926 514 4151204550619 515 4158411157982 516 4277041602808 517 4401182289514 518 4438049285853 519 4355923939106 520 4208710765184 521 4123070041084 522 4252937907804 523 4721840948460 524 5577013739580 525 6771130632756 526 8174424081568 527 9609385522546 528 10895233271628 529 11888943360472 530 12511872118988 531 12755094843622 532 12662909870740 533 12302144329596 534 11732110039376 535 10991343595394 536 10108954804998 537 9132771850196 538 8152979687241 539 7299680553952 540 6708951871102 541 6474974231024 542 6619067227621 543 7098985293976 544 7856941640158 545 8878064272776 546 10219467824813 547 11982272657952 548 14230264921592 549 16893999430892 550 19717595915481 551 22292028449558 552 24175104001917 553 25047933011290 554 24833478009555 555 23722610831018 556 22103111541547 557 20431543119616 558 19100126244935 559 18334526202032 560 18139220631353 561 18301745405006 562 18466625826477 563 18273556134350 564 17519395589043 565 16274824167840 566 14895087743747 567 13914680110894 568 13876647001396 569 15175560131926 570 17970813129248 571 22175156097412 572 27484579089414 573 33416966706252 574 39358400074884 575 44640895633508 576 48664306817048 577 51033698859646 578 51649054081000 579 50693242043788 580 48519228374406 581 45501590857474 582 41941910080848 583 38080026778280 584 34185971022411 585 30643861704804 586 27936545126947 587 26505466188398 588 26553964573171 589 27921057650914 590 30132759483931 591 32643457663690 592 35162282806955 593 37887391138858 594 41491933710279 595 46819281948968 596 54401582628057 597 64033923022700 598 74642149210169 599 84553181234726 600 92069392946341 601 96080649126826 602 96425959408586 603 93858194540722 604 89675742493338 605 85227516287294 606 81499050425682 607 78887619024180 608 77174792104064 609 75668091469730 610 73485266960852 611 69932590925830 612 64866758689210 613 58886584507800 614 53246463123896 615 49518407253554 616 49165497512589 617 53221937084908 618 62175265508948 619 75993352687876 620 94156649237350 621 115610730675740 622 138694725948496 623 161199913904600 624 180673384108116 625 194924669226968 626 202539793510642 627 203175845235976 628 197521148031868 629 186979966503744 630 173265836188700 631 158098739249444 632 143101648535219 633 129838324438096 634 119815138895794 635 114272803845468 636 113749889157124 637 117632608678850 638 124050855473750 639 130395303318602 640 134412905054362 641 135457091879494 642 135262805788940 643 137737053196710 644 147672106489080 645 168807372532470 646 202034546461960 647 244564183749108 648 290501452052443 649 332653993976674 650 364812847569381 651 383530024293772 652 388708069565085 653 382950758181568 654 370201347496802 655 354368336414286 656 338381827661128 657 323735037041028 658 310384797443890 659 296980105657236 660 281519974994658 661 262441202992858 662 239806620817156 663 216002361365998 664 195465412114414 665 183459470620596 666 184473557639129 667 201034351073760 668 233440138023489 669 280336948499514 670 339564475311004 671 408620346306978 672 484456686343896 673 562868001114776 674 638083774903662 675 703116272119464 676 750987779546918 677 776444404185572 678 777455053596782 679 755851246441854 680 716845438560454 681 667675294451510 682 615988878672197 683 568591060015048 684 530795896548217 685 506133923503938 686 495953057213448 687 498755996084124 688 509732862870666 689 521334575780080 690 525440465173046 691 516758149818084 692 496131382164106 693 472101021633368 694 459640158181852 695 476161494319120 696 536047692611110 697 645563905960090 698 799904136332061 699 983424367471676 700 1173080722846433 701 1344024639360236 702 1475562144846089 703 1555585786134534 704 1582230988411476 705 1562608236661770 706 1509468300250707 707 1437116130893878 708 1357752305738534 709 1279013417945810 710 1203149770466166 711 1128058955881164 712 1050045606866146 713 967534866558130 714 884262263667194 715 810258268245712 716 759682292772346 717 746095698338996 718 777312706026261 719 852545509034772 720 963623815033564 721 1099944600691560 722 1254597407526545 723 1428115768960784 724 1627265581974806 725 1858863672679478 726 2121502526488796 727 2399622123280874 728 2663631311791400 729 2876986915945734 730 3007672381758262 731 3039171354378230 732 2976070213439200 733 2841913801013350 734 2670643924526703 735 2495886901566148 736 2342857831521984 737 2225447017649378 738 2147631505587851 739 2106088142996218 740 2091352138625178 741 2087559304777386 742 2073412227696050 743 2027191081006420 744 1935971171109210 745 1805613264739428 746 1666282069473722 747 1569626137739632 748 1577416739560160 749 1745079199416218 750 2105275733547345 751 2656235240427900 752 3357866121058728 753 4136861331773702 754 4900229065161365 755 5554648534522404 756 6026877428238747 757 6279171749760784 758 6314644625575981 759 6170971571516926 760 5905376774165871 761 5576965862977794 762 5232570336365179 763 4899738954905532 764 4587305787729192 765 4291834872694610 766 4007411707679680 767 3735778074889254 768 3493128242714734 769 3309819248420918 770 3221253457839554 771 3252533212772182 772 3404164406319263 773 3647772014236046 774 3937246813256589 775 4232839021835582 776 4527443368712855 777 4860643109989974 778 5309941277194569 779 5958947109227714 780 6854276297341828 781 7970350315368610 782 9199810768508460 783 10376867567431338 784 11326120711378434 785 11917310348060396 786 12103234054482694 787 11925770225762456 788 11490037111531305 789 10921447153383678 790 10326767390782355 791 9774780499297034 792 9298465858848615 793 8907832540440390 794 8599089996928265 795 8353482762073700 796 8131391124283614 797 7874341070838244 798 7523662653917670 799 7052478922279408 800 6496435524857712 801 5966204317426288 802 5632739385342484 803 5688926710612608 804 6300795530680555 805 7563399707041648 806 9472045073174507 807 11913418632848828 808 14677229699065521 809 17487381969166592 810 20049628950733989 811 22107778365027834 812 23494242952385519 813 24158210481255158 814 24160604480272302 815 23638533969094406 816 22755706848553540 817 21660220420804316 818 20463833744709012 819 19242835716001420 820 18050148215026163 821 16927668018023630 822 15914536225084448 823 15052836017913094 824 14391467701128478 825 13983808945892252 826 13872868118553092 827 14064341015532068 828 14500527751533969 829 15056783804486494 830 15577723337772604 831 15951318313782056 832 16194130309866434 833 16504692577970520 834 17246305135025260 835 18846897527210836 836 21641745951757913 837 25716723416985406 838 30818587552397136 839 36377553813072288 840 41643267562520222 841 45887470102028050 842 48597783439834264 843 49591789295413528 844 49017197824694431 845 47254043078623798 846 44772938328144030 847 42010945961305590 848 39302787333459122 849 36867140969238038 850 34819906128664056 851 33184360900892820 852 31889509202667103 853 30773950918030488 854 29622077575453630 855 28243604538915116 856 26576416910528438 857 24768010396883846 858 23190562830176448 859 22371342116823852 860 22859208049340871 861 25077353028329608 862 29216118396393344 863 35196941918080888 864 42703673279632000 865 51251237286731260 866 60257764300514342 867 69103004604254480 868 77177248902547733 869 83933489404218254 870 88946006943143941 871 91962321673489272 872 92929674360122259 873 91988257951830352 874 89440258724778540 875 85709141572850832 876 81292773635532974 877 76701374595004196 878 72376279530944357 879 68609974408249476 880 65509264869241949 881 63033696295297038 882 61096047983335242 883 59661217533777518 884 58768226091884536 885 58447677142555170 886 58588135585446249 887 58862340404230016 888 58810558187807251 889 58092646120782974 890 56810927696796120 891 55738785130815188 892 56306172547293302 893 60286780632027298 894 69257376158777497 895 84002453280817798 896 104076552626516739 897 127698422266824858 898 152047174429768320 899 173893699726641256 900 190378646210899926 901 199689963987336096 902 201426624622698677 903 196550756010338202 904 186980169248174439 905 174992869042118444 906 162655912417506626 907 151443332311324770 908 142104197285651344 909 134738050960943614 910 128979948006273059 911 124207080663248290 912 119729501400331915 913 114972322613425454 914 109660214164331304 915 103977762541018004 916 98638091043804352 917 94791823093694388 918 93766077042916545 919 96711604312572086 920 104299645735653871 921 116601227067569070 922 133194872140432202 923 153427880279684030 924 176671126968022828 925 202412153371667940 926 230129599039257115 927 259029324381423194 928 287816308390202115 929 314668195165989668 930 337472158090865573 931 354253074376795936 932 363636329943428764 933 365187649159806120 934 359530427764422257 935 348209747305729836 936 333328492606416968 937 317037354494538216 938 301026961684138705 939 286213981630741152 940 272770615561530022 941 260491730927458246 942 249291968287745547 943 239513451189569828 944 231811142022344916 945 226647308605693280 946 223712360930274067 947 221703696164839790 948 218744245837057920 949 213382677706551358 950 205779365970301133 951 198529549343540742 952 196675965840326528 953 206753196035145172 954 235051619667030769 955 285569566005921718 956 358267880665299002 957 448220532425420522 958 546055892841657579 959 639723914181780986 960 717185831736963018 961 769257071076647056 962 791710117530055433 963 785955542424912044 964 758112801546069448 965 716864137443105368 966 670907074448777315 967 626900586252088028 968 588509038757611898 969 556631074795923962 970 530408867788548847 971 508379764421303024 972 489248082635038068 973 472115937492406268 974 456381093338607691 975 441662439615259366 976 427978388845649670 977 416102428287096866 978 407782037540012125 979 405513815071612294 980 411833725219054252 981 428442038172424262 982 455691101944459555 983 492843876217521382 984 539078358060630564 985 594696706473555784 986 661727038353107679 987 743307902324834532 988 841873896964265568 989 956882592319203044 990 1083204632188407623 991 1211086825758082480 992 1327893617900564195 993 1421028742500437752 994 1480960967436046409 995 1503320384197450014 996 1489483451737905801 997 1445645378264226516 998 1380843459421645225 999 1304641660376105596 1000 1225211004301155121 1001 1148351148086894818 1002 1077610078092662573 1003 1015166481373211624 1004 962762858124275299 1005 921967397945554182 1006 893486591785767693 1007 875944465622202106 1008 865071297923582675 1009 854236616528756374 1010 836657621842337823 1011 808721055476625908 1012 773159229025671419 1013 740686447686317342 1014 729178357382640369 1015 760308884533459768 1016 854379980114292351 1017 1024618642665816560 1018 1272391545428176457 1019 1584647323843439210 1020 1934499974494932795 1021 2285230635975441332 1022 2597138044249171895 1023 2835756365934298758 1024 2979286172451628375 1025 3023011125662605048 1026 2979213723392284183 1027 2872537282859889462 1028 2732371955264221759 1029 2584967146569198096 1030 2448010895172301651 1031 2329250229099710822 1032 2228852468419424929 1033 2143560541068227356 1034 2070162930393667099 1035 2006674472361614750