0 1 1 1 2 2 3 2 4 4 5 4 6 6 7 8 8 12 9 15 10 19 11 24 12 30 13 36 14 47 15 57 16 74 17 88 18 112 19 130 20 160 21 190 22 232 23 277 24 333 25 399 26 471 27 554 28 656 29 768 30 908 31 1060 32 1256 33 1452 34 1702 35 1968 36 2294 37 2646 38 3068 39 3549 40 4093 41 4710 42 5418 43 6211 44 7121 45 8138 46 9331 47 10625 48 12150 49 13817 50 15749 51 17858 52 20290 53 23000 54 26054 55 29477 56 33341 57 37653 58 42480 59 47864 60 53934 61 60621 62 68203 63 76572 64 86017 65 96388 66 108072 67 120964 68 135343 69 151264 70 169031 71 188702 72 210533 73 234700 74 261530 75 291059 76 323897 77 360055 78 400214 79 444322 80 493306 81 547109 82 606559 83 671892 84 744072 85 823386 86 910768 87 1006847 88 1112620 89 1228578 90 1356180 91 1496028 92 1649764 93 1818017 94 2003017 95 2205391 96 2427395 97 2670129 98 2936261 99 3227019 100 3545290 101 3893075 102 4273545 103 4688742 104 5142648 105 5637755 106 6178423 107 6767566 108 7410775 109 8111292 110 8875227 111 9706843 112 10613324 113 11599283 114 12672791 115 13840083 116 15110280 117 16490309 118 17991168 119 19621248 120 21392570 121 23314939 122 25402800 123 27667435 124 30125060 125 32789619 126 35680135 127 38812028 128 42207025 129 45883844 130 49867291 131 54178434 132 58846715 133 63897254 134 69362880 135 75272891 136 81665425 137 88574221 138 96042133 139 104109524 140 112826164 141 122237715 142 132401391 143 143370746 144 155211143 145 167982736 146 181761883 147 196618824 148 212639802 149 229906299 150 248517556 151 268567472 152 290167501 153 313427455 154 338475032 155 365435303 156 394454692 157 425678000 158 459272767 159 495402261 160 534259905 161 576033090 162 620940938 163 669198521 164 721056974 165 776763345 166 836600850 167 900854831 168 969847180 169 1043902533 170 1123387093 171 1208673512 172 1300179516 173 1398326691 174 1503594025 175 1616461840 176 1737472525 177 1867172324 178 2006179260 179 2155116714 180 2314682681 181 2485591510 182 2668634389 183 2864622529 184 3074451099 185 3299044308 186 3539417432 187 3796615712 188 4071795784 189 4366144173 190 4680969523 191 5017614737 192 5377564103 193 5762339710 194 6173615634 195 6613122812 196 7082754555 197 7584471210 198 8120409403 199 8692791570 200 9304030139 201 9956632137 202 10653328314 203 11396953815 204 12190590487 205 13037438397 206 13940980621 207 14904828899 208 15932903199 209 17029285132 210 18198393716 211 19444833318 212 20773579127 213 22189830517 214 23699188551 215 25307504763 216 27021088465 217 28846531470 218 30790929257 219 32861699481 220 35066832758 221 37414675316 222 39914202055 223 42574805049 224 45406570143 225 48420050395 226 51626569128 227 55037995078 228 58667042516 229 62527035115 230 66632248161 231 70997642768 232 75639222697 233 80573770801 234 85819242808 235 91394465004 236 97319555743 237 103615633248 238 110305244934 239 117412047064 240 124961284641 241 132979465186 242 141494852968 243 150537120706 244 160137912457 245 170330452135 246 181150126491 247 192634102860 248 204821957629 249 217755259331 250 231478230053 251 246037360363 252 261482077343 253 277864325514 254 295239311278 255 313665066686 256 333203235325 257 353918595139 258 375879968979 259 399159679247 260 423834506692 261 449985153831 262 477697268576 263 507060872248 264 538171425433 265 571129325219 266 606040979044 267 643018281790 268 682179796647 269 723650214537 270 767561603944 271 814052810181 272 863270905278 273 915370487370 274 970515242569 275 1028877250557 276 1090638664347 277 1155990972950 278 1225136745856 279 1298289011294 280 1375673010356 281 1457525596751 282 1544097140866 283 1635650946682 284 1732465260911 285 1834832627130 286 1943062189650 287 2057478909921 288 2178426079883 289 2306264544454 290 2441375445967 291 2584159394449 292 2735039355632 293 2894459984888 294 3062890556585 295 3240824367850 296 3428781886574 297 3627310249088 298 3836986577407 299 4058417467871 300 4292242732907 301 4539134741982 302 4799802502674 303 5074991020507 304 5365485783514 305 5672112077992 306 5995739782424 307 6337282932479 308 6697704664100 309 7078016919106 310 7479285733775 311 7902631151336 312 8349232789107 313 8820329870749 314 9317227420792 315 9841296234644 316 10393979603071 317 10976793391875 318 11591333408662 319 12239275483744 320 12922383418800 321 13642509460246 322 14401602664539 323 15201709640120 324 16044983550223 325 16933685229161 326 17870192690084 327 18857002558542 328 19896740537766 329 20992162993376 330 22146168280463 331 23361798707600 332 24642252886882 333 25990887888271 334 27411232571623 335 28906990407269 336 30482053673462 337 32140506805403 338 33886641805121 339 35724962290941 340 37660199911595 341 39697319049008 342 41841534763339 343 44098318028299 344 46473415085802 345 48972853620984 346 51602963789673 347 54370385103883 348 57282089109214 349 60345387525748 350 63567956507395 351 66957845819692 352 70523505268842 353 74273795197731 354 78218014917516 355 82365914499989 356 86727725869718 357 91314175792208 358 96136519393024 359 101206555009155 360 106536660505747 361 112139809876018 362 118029612397775 363 124220331735888 364 130726927923989 365 137565078592527 366 144751224657360 367 152302594028342 368 160237251001482 369 168574122506458 370 177333052224360 371 186534829354122 372 196201247106646 373 206355134962411 374 217020421964725 375 228222172532502 376 239986654671889 377 252341380595725 378 265315180001780 379 278938245094488 380 293242210190779 381 308260201534989 382 324026923426914 383 340578712902290 384 357953634068163 385 376191537803986 386 395334164106354 387 415425208263749 388 436510431773096 389 458637735247051 390 481857278016708 391 506221559739401 392 531785549062664 393 558606773822465 394 586745460681329 395 616264634630218 396 647230270069248 397 679711399676717 398 713780279442409 399 749512507217130 400 786987201962723 401 826287134224889 402 867498920784361 403 910713167712039 404 956024680676870 405 1003532623463487 406 1053340744478399 407 1105557551158838 408 1160296555497999 409 1217676465962945 410 1277821453156127 411 1340861359698300 412 1406931989704064 413 1476175337124281 414 1548739899943148 415 1624780930188001 416 1704460775242194 417 1787949151000587 418 1875423511423839 419 1967069349162563 420 2063080594386328 421 2163659944033223 422 2269019293828898 423 2379380099188331 424 2494973842578621 425 2616042427822747 426 2742838688430375 427 2875626816701622 428 3014682914992792 429 3160295464149679 430 3312765921777669 431 3472409232597204 432 3639554476632897 433 3814545428203345 434 3997741256699661 435 4189517136880384 436 4390265008020576 437 4600394240513056 438 4820332456924615 439 5050526258786859 440 5291442118082183 441 5543567167992501 442 5807410169001316 443 6083502370858454 444 6372398559977445 445 6674677996924383 446 6990945550712476 447 7321832721796733 448 7667998869182124 449 8030132324471164 450 8408951721561342 451 8805207210236392 452 9219681894657226 453 9653193153600081 454 10106594200214569 455 10580775516621283 456 11076666542843981 457 11595237238369468 458 12137499911728214 459 12704510917275126 460 13297372635402954 461 13917235319390077 462 14565299237077685 463 15242816677774625 464 15951094272100037 465 16691495173577976 466 17465441568824297 467 18274417046772912 468 19119969318289580 469 20003712786896476 470 20927331491282217 471 21892581898582695 472 22901296089012393 473 23955384788085561 474 25056840811457766 475 26207742359942122 476 27410256743589358 477 28666643956625170 478 29979260707941603 479 31350564299957400 480 32783116988496559 481 34279590188913799 482 35842769196979087 483 37475557747035975 484 39180983117369338 485 40962201074353331 486 42822501393313643 487 44765313218454054 488 46794211030686441 489 48912920463632577 490 51125324752188147 491 53435471035645344 492 55847577330963114 493 58366039361949716 494 60995438097188313 495 63740547145067863 496 66606340909185503 497 69598002593147758 498 72720933016365869 499 75980759284400427 500 79383344316278661 501 82934796231506137 502 86641478641313870 503 90510020818959785 504 94547328813142952 505 98760596458534883 506 103157317384083332 507 107745296929787263 508 112532665117805399 509 117527889541978089 510 122739789387647589 511 128177549368350569 512 133850734871079401 513 139769307032570561 514 145943639097944588 515 152384532724231075 516 159103235640543552 517 166111459286872484 518 173421397872778137 519 181045747451053590 520 188997726494395451 521 197291096517961503 522 205940184290197436 523 214959904118422263 524 224365781833171485 525 234173978860834556 526 244401318112426707 527 255065309993907829 528 266184180349442707 529 277776898559078587 530 289863207688521191 531 302463654851168627 532 315599623726704458 533 329293367355951058 534 343568043221347187 535 358447748666856839 536 373957558735908303 537 390123564413786336 538 406972913452044959 539 424533851643442337 540 442835766853064320 541 461909233569872257 542 481786060393890242 543 502499338113894832 544 524083490910165332 545 546574328249717772 546 570009100080721076 547 594426552829393115 548 619866988900752669 549 646372327094940588 550 673986166736945481 551 702753852845734686 552 732722545267452051 553 763941288954785848 554 796461088474490090 555 830334983798869538 556 865618130598795213 557 902367881958667541 558 940643874887202525 559 980508118430103489 560 1022025086864003362 561 1065261814684061225 562 1110287997001432978 563 1157176091931596020 564 1206001428727735752 565 1256842318122582658 566 1309780168803642753 567 1364899606305511458 568 1422288598444323120 569 1482038583426443263 570 1544244604922008002 571 1609005450072990251 572 1676423794919881345 573 1746606353076965027 574 1819664032281705742 575 1895712094525795900 576 1974870324584911898 577 2057263202473945283 578 2143020084842116893 579 2232275390666795075 580 2325168796496962763 581 2421845436368205028 582 2522456111907595877 583 2627157507561366832 584 2736112416677164162 585 2849489973179211869 586 2967465894807115604 587 3090222732490466480 588 3217950132007351681 589 3350845102349838086 590 3489112297198588728 591 3632964303697793555 592 3782621945207396729 593 3938314591994610231 594 4100280486869251212 595 4268767079405324959 596 4444031376117599832 597 4626340299986020116 598 4815971066986326902 599 5013211572781148586 600 5218360797536824840 601 5431729221826575249 602 5653639261804536995 603 5884425716438713194 604 6124436235306273154 605 6374031799457942691 606 6633587224219120661 607 6903491676143449320 608 7184149213432843150 609 7475979341620208621 610 7779417594326467250 611 8094916130548566665 612 8422944358693225277 613 8763989578501498529 614 9118557651494551560 615 9487173690850860780 616 9870382781636690785 617 10268750722102523576 618 10682864797367759273 619 11113334575874331980 620 11560792740394171709 621 12025895943620508097 622 12509325700715694498 623 13011789308321575419 624 13534020803077367012 625 14076781948704850694 626 14640863265267899490 627 15227085089248259791 628 15836298678618323097 629 16469387351247779841 630 17127267671236197137 631 17810890671276122687 632 18521243126164225487 633 19259348865181818039 634 20026270139047031949 635 20823109028753580011 636 21651008912744569685 637 22511155979109964793 638 23404780800137084413 639 24333159955353269932 640 25297617721162912636 641 26299527812677849867 642 27340315196638965549 643 28421457960616725374 644 29544489257983736521 645 30710999313546951334 646 31922637510057306647 647 33181114540033695407 648 34488204643892551541 649 35845747918358340034 650 37255652717096757139 651 38719898126815368754 652 40240536541899014165 653 41819696320180835096 654 43459584543947986126 655 45162489868130636613 656 46930785480865751241 657 48766932157858859537 658 50673481436594473311 659 52653078891416550622 660 54708467536546527621 661 56842491337503805122 662 59058098859060931498 663 61358347029672414552 664 63746405051761570150 665 66225558436973748404 666 68799213197218687333 667 71470900169888787338 668 74244279509412434976 669 77123145322790394112 670 80111430482734911098 671 83213211595450948976 672 86432714157900512560 673 89774317881090509241 674 93242562215656562458 675 96842152055580552556 676 100577963657805824236 677 104455050752958729562 678 108478650886650608513 679 112654191965624726111 680 116987299050123544235 681 121483801365962307984 682 126149739579427028604 683 130991373307689141272 684 136015188909766170468 685 141227907530079403627 686 146636493441324251249 687 152248162658165864343 688 158070391870477876242 689 164110927666802283904 690 170377796098844815320 691 176879312556922987683 692 183624092009547942106 693 190621059575964084850 694 197879461487413113659 695 205408876405132228650 696 213219227153202239293 697 221320792833465004307 698 229724221383140847213 699 238440542541768639030 700 247481181290366962642 701 256857971728961242990 702 266583171458116065145 703 276669476429745414421 704 287130036335772686081 705 297978470499072161598 706 309228884338557769983 707 320895886371587537398 708 332994605829116882896 709 345540710845915301040 710 358550427304547702386 711 372040558294709329261 712 386028504270038069453 713 400532283863556842852 714 415570555446949207387 715 431162639394540420588 716 447328541140882139993 717 464088974992050494516 718 481465388783599386027 719 499479989344519590118 720 518155768864728477673 721 537516532124103944235 722 557586924685540934188 723 578392462009194740205 724 599959559594990877237 725 622315564109967489000 726 645488785612313526932 727 669508530828551587358 728 694405137600044319548 729 720210010455418204034 730 746955657430101751011 731 774675728089150086468 732 803405052880054082349 733 833179683771293912940 734 864036936309644718290 735 896015433050848545944 736 929155148503549432347 737 963497455540483981161 738 999085173423339702236 739 1035962617394951186803 740 1074175649992012716938 741 1113771734032361907946 742 1154799987436222928258 743 1197311239836335249366 744 1241358091143371668744 745 1286994972021850054121 746 1334278206450500999642 747 1383266076322622728198 748 1434018888269006888893 749 1486599042658430027927 750 1541071104967819488164 751 1597501879477168006058 752 1655960485490548875778 753 1716518436038679080759 754 1779249719274011926153 755 1844230882515040653599 756 1911541119159803637116 757 1981262358427272157317 758 2053479358156625964247 759 2128279800624604743288 760 2205754391621576810338 761 2285996962748215930497 762 2369104577185310012178 763 2455177638899317420796 764 2544320005549292966507 765 2636639105059327922713 766 2732246056135152793087 767 2831255792690931963159 768 2933787192478633188885 769 3039963209888856022781 770 3149911013228616083023 771 3263762126448778184914 772 3381652575641061028633 773 3503723040280755843290 774 3630119009550338169863 775 3760990943724108591976 776 3896494440965783760868 777 4036790409522185995133 778 4182045245683144142248 779 4332431017494851929291 780 4488125654615081801887 781 4649313144302140093386 782 4816183733945474314480 783 4988934140135666002842 784 5167767764700816899350 785 5352894917714014905652 786 5544533047919762743386 787 5742906980590643896458 788 5948249163284155276235 789 6160799919518564381806 790 6380807710861693815664 791 6608529407458329233910 792 6844230567515892599392 793 7088185725782522456629 794 7340678691563070656310 795 7602002856316452163472 796 7872461511407483679524 797 8152368176067586070307 798 8442046936165139076534 799 8741832793852235945720 800 9052072028718896575497 801 9373122570533411190614 802 9705354384231866332783 803 10049149867248794803783 804 10404904259886582779224 805 10773026068828444755211 806 11153937504529550996218 807 11548074932606531757673 808 11955889339997150651499 809 12377846816027246201088 810 12814429049196159721077 811 13266133839836914226910 812 13733475629502255284067 813 14216986047254030271365 814 14717214473750801097559 815 15234728623332058694678 816 15770115145040474177475 817 16323980242803153387104 818 16896950315763445560391 819 17489672619006688408930 820 18102815945724833626566 821 18737071331089537198704 822 19393152778932774318199 823 20071798011533394354944 824 20773769243665701400204 825 21499853981240715171356 826 22250865845754037812216 827 23027645424906183825226 828 23831061150672487507769 829 24662010205223796701337 830 25521419456042629952013 831 26410246420673826945197 832 27329480262527206575183 833 28280142818209135443276 834 29263289657878013366644 835 30280011179143518077807 836 31331433736083677617467 837 32418720803946773786411 838 33543074181195399621155 839 34705735229512176140733 840 35907986153509185249904 841 37151151320817656028892 842 38436598624391634170426 843 39765740887760192890623 844 41140037315159879659217 845 42560994987343817301105 846 44030170405104969862798 847 45549171081372686590994 848 47119657184032848736960 849 48743343230400087123309 850 50421999835608208849832 851 52157455515922616845918 852 53951598549362820586521 853 55806378894722124325560 854 57723810171497482124346 855 59705971701907145325110 856 61755010617643225807738 857 63873144032630013224521 858 66062661284577782676215 859 68325926246702061449095 860 70665379712551711045579 861 73083541855417363483293 862 75583014765427782400108 863 78166485065916553023431 864 80836726612336585993542 865 83596603275423928859544 866 86449071812067400298820 867 89397184825715684319999 868 92444093819962747010150 869 95593052347284363081112 870 98847419256763922450695 871 102210662042927306702547 872 105686360299734066223038 873 109278209282001062502723 874 112990023578529665601911 875 116825740899374087995810 876 120789425981760944487928 877 124885274617272469634393 878 129117617805052561562949 879 133490926033834959876524 880 138009813697815862333527 881 142679043649372302927043 882 147503531893920845341769 883 152488352430135524799028 884 157638742241110209552641 885 162960106439912466214969 886 168458023575421768638139 887 174138251102142460987519 888 180006731020212345961186 889 186069595689550206559376 890 192333173824711991725447 891 198803996674671304395644 892 205488804394458642689788 893 212394552613165408703915 894 219528419205633500412316 895 226897811272648517985719 896 234510372337359421863781 897 242373989763076557915477 898 250496802400599182333661 899 258887208470574795084402 900 267553873689494601994725 901 276505739645201303877760 902 285752032430995778431383 903 295302271544610124150729 904 305166279061645135163037 905 315354189090159619274123 906 325876457516544569978562 907 336743872049816429116782 908 347967562575029150306144 909 359559011823417720399219 910 371530066370565519134299 911 383892947970718388080527 912 396660265239169035356444 913 409845025691369936321996 914 423460648151366040324931 915 437520975538775086246669 916 452040288047616235725112 917 467033316726813402692485 918 482515257476425730098732 919 498501785470073340725393 920 515009070018397582107316 921 532053789884706168964936 922 549653149068474400740563 923 567824893068581165804373 924 586587325642823032715922 925 605959326076360379528078 926 625960366976567929492938 927 646610532607757833289657 928 667930537784231142904667 929 689941747335989731644116 930 712666196166608141243273 931 736126609918505868202554 932 760346426266224686710934 933 785349816853923882402633 934 811161709898856496457888 935 837807813478073669900224 936 865314639521343867976480 937 893709528528636115324947 938 923020675036437343253311 939 953277153852423988818275 940 984508947084123282326098 941 1016746971982315857968960 942 1050023109626261784436830 943 1084370234472806682704678 944 1119822244797984964746337 945 1156414094054549079316605 946 1194181823175666135955594 947 1233162593849674933023394 948 1273394722797849766015198 949 1314917717081620865923498 950 1357772310472998556466361 951 1402000500916309026694974 952 1447645589116878512419173 953 1494752218286533934375743 954 1543366415083562755872992 955 1593535631778852599907363 956 1645308789687978024338745 957 1698736323902916899550643 958 1753870229365418381142627 959 1810764108317769259572702 960 1869473219175366979472873 961 1930054526859042219534231 962 1992566754634046654731891 963 2057070437495979970664459 964 2123627977153219448942108 965 2192303698648606693049082 966 2263163908672736557694095 967 2336276955614235836960353 968 2411713291402324990178273 969 2489545535189824058077623 970 2569848538935014761579221 971 2652699454933455191924069 972 2738177805361465905875968 973 2826365553885474863118758 974 2917347179402441141118898 975 3011209751968827521769863 976 3108043010987025478403142 977 3207939445710181210804456 978 3310994378138215339729700 979 3417306048369679467570810 980 3526975702486331673494645 981 3640107683038994020731246 982 3756809522215904860255198 983 3877192037766263174637461 984 4001369431764755046125668 985 4129459392294133046391394 986 4261583198136485208060932 987 4397865826554871909120998 988 4538436064261096256514567 989 4683426621656173790119558 990 4832974250444669991906954 991 4987219864714645810470993 992 5146308665590085460771938 993 5310390269553032695766984 994 5479618840548313188710671 995 5654153225973882446911657 996 5834157096676029839763418 997 6019799091058613080880172 998 6211252963432266350505507 999 6408697736719247173459222 1000 6612317859646965675508367