0 1 1 1 2 1 3 3 4 3 5 5 6 8 7 10 8 13 9 18 10 27 11 32 12 44 13 55 14 73 15 97 16 121 17 151 18 194 19 240 20 299 21 384 22 465 23 576 24 706 25 869 26 1051 27 1293 28 1572 29 1896 30 2290 31 2761 32 3302 33 3973 34 4732 35 5645 36 6759 37 7995 38 9477 39 11218 40 13258 41 15597 42 18393 43 21565 44 25319 45 29703 46 34701 47 40478 48 47278 49 54985 50 63955 51 74275 52 86156 53 99723 54 115455 55 133467 56 153978 57 177595 58 204481 59 235229 60 270402 61 310439 62 355903 63 407970 64 466846 65 533947 66 610258 67 696549 68 794283 69 905396 70 1030716 71 1172654 72 1333005 73 1514149 74 1718150 75 1948957 76 2208195 77 2500598 78 2830092 79 3199838 80 3615514 81 4083063 82 4607201 83 5195314 84 5855223 85 6593997 86 7421567 87 8348103 88 9384082 89 10541924 90 11837340 91 13282964 92 14895970 93 16696607 94 18704012 95 20940498 96 23433676 97 26207497 98 29295632 99 32730498 100 36549492 101 40791935 102 45507822 103 50740249 104 56548734 105 62994076 106 70138511 107 78056048 108 86831688 109 96546452 110 107301921 111 119204455 112 132367412 113 146920791 114 163008871 115 180779333 116 200403667 117 222072413 118 245979897 119 272354054 120 301443624 121 333501852 122 368829089 123 407750098 124 450601009 125 497773998 126 549687104 127 606788964 128 669580348 129 738618468 130 814476023 131 897818836 132 989351930 133 1089844195 134 1200133047 135 1321163247 136 1453905502 137 1599463832 138 1759035979 139 1933906595 140 2125485632 141 2335331346 142 2565080227 143 2816578180 144 3091805639 145 3392900624 146 3722203264 147 4082289047 148 4475884738 149 4906013204 150 5375958694 151 5889233741 152 6449705363 153 7061586055 154 7729346236 155 8457957643 156 9252775520 157 10119547135 158 11064578606 159 12094714291 160 13217290652 161 14440321981 162 15772523256 163 17223219661 164 18802629964 165 20521784927 166 22392563416 167 24427880320 168 26641796129 169 29049282022 170 31666793668 171 34512029960 172 37604019810 173 40963477882 174 44612840620 175 48576108716 176 52879488020 177 57551164770 178 62621530120 179 68123475385 180 74092647046 181 80567151035 182 87588502218 183 95201378497 184 103453826186 185 112397852501 186 122089634798 187 132589386170 188 143962426254 189 156279050267 190 169614857992 191 184051418373 192 199676902573 193 216585706994 194 234880035638 195 254669854727 196 276073248542 197 299217655910 198 324240405595 199 351288714951 200 380521550565 201 412109904228 202 446237227055 203 483101377554 204 522915089249 205 565906651567 206 612321882309 207 662425264222 208 716500182139 209 774852051389 210 837808876779 211 905722282197 212 978970762383 213 1057961000916 214 1143128496911 215 1234942086526 216 1333904692092 217 1440555630088 218 1555474207607 219 1679282527352 220 1812646557938 221 1956282238832 222 2110957087294 223 2277493531573 224 2456774169623 225 2649745982440 226 2857422100611 227 3080890523036 228 3321316827329 229 3579949092096 230 3858125647334 231 4157280848309 232 4478948518751 233 4824774661712 234 5196520747131 235 5596071960954 236 6025447783457 237 6486811173580 238 6982474158584 239 7514914301931 240 8086782139398 241 8700912089520 242 9360338386311 243 10068307522946 244 10828288491189 245 11643995117677 246 12519397817878 247 13458739331085 248 14466558663393 249 15547707862463 250 16707369775527 251 17951086514768 252 19284780953254 253 20714777688235 254 22247836942935 255 23891181097032 256 25652519810145 257 27540091333367 258 29562693619050 259 31729715121368 260 34051185264287 261 36537809760438 262 39201011781831 263 42052987207629 264 45106752702278 265 48376190971848 266 51876120949198 267 55622350582417 268 59631738300675 269 63922269674507 270 68513128738953 271 73424763395895 272 78678986231657 273 84299051695689 274 90309743730489 275 96737486869229 276 103610448442547 277 110958633958420 278 118814032518967 279 127210723751226 280 136185011713908 281 145775576161622 282 156023623907527 283 166973028516165 284 178670530346347 285 191165898798644 286 204512119557802 287 218765612721431 288 233986448039453 289 250238549055620 290 267589973841836 291 286113149496037 292 305885141545287 293 326987964310985 294 349508883050134 295 373540717568829 296 399182227211327 297 426538458238906 298 455721120768224 299 486849032833044 300 520048548726688 301 555453993294482 302 593208208929971 303 633463047712714 304 676379909166540 305 722130369471579 306 770896784753696 307 822872923753937 308 878264719680253 309 937290983386200 310 1000184164822618 311 1067191237539909 312 1138574552338106 313 1214612743970596 314 1295601775986205 315 1381855964287398 316 1473709044644224 317 1571515422914588 318 1675651379261656 319 1786516353476275 320 1904534408114302 321 2030155672331217 322 2163857859470719 323 2306148011155506 324 2457564194020256 325 2618677325220667 326 2790093196120942 327 2972454542224242 328 3166443147841514 329 3372782299826812 330 3592239170584971 331 3825627390657808 332 4073809875133916 333 4337701714734558 334 4618273154250099 335 4916553007053092 336 5233631990486707 337 5570666346678208 338 5928881771812532 339 6309577470922142 340 6714130333031758 341 7143999664728838 342 7600731886490538 343 8085965577803147 344 8601436944891913 345 9148985477742147 346 9730559800068799 347 10348224230800589 348 11004165347761143 349 11700699000410678 350 12440277937092833 351 13225499650131776 352 14059114547312076 353 14944035041442466 354 15883344679868340 355 16880307919850647 356 17938380664310149 357 19061221174988607 358 20252701458124119 359 21516919780145985 360 22858213400035575 361 24281172077600100 362 25790652697872660 363 27391794350829107 364 29090034139320080 365 30891124435480138 366 32801150536962706 367 34826549364131323 368 36974129620221518 369 39251092630723365 370 41665054256446809 371 44224068610460229 372 46936652495569843 373 49811811185350595 374 52859066214736270 375 56088484111597000 376 59510706626371760 377 63136983347179185 378 66979205406101338 379 71049940937023335 380 75362473358777019 381 79930840795300790 382 84769877819221724 383 89895260113557873 384 95323550865032926 385 101072249518645382 386 107159844227782795 387 113605866047771358 388 120430946252884078 389 127656877456537692 390 135306677366956557 391 143404655573871763 392 151976485391502452 393 161049278090534433 394 170651661459742429 395 180813863394223265 396 191567799112180467 397 202947162654359487 398 214987524968718144 399 227726435447537955 400 241203529356650931 401 255460641875028355 402 270541927287237160 403 286493983984296850 404 303365988091746099 405 321209832188832319 406 340080271781180213 407 360035080672472474 408 381135213538165640 409 403444976215142211 410 427032207625760295 411 451968468667859019 412 478329241723180751 413 506194141938498640 414 535647138253577960 415 566776785335174212 416 599676470442146009 417 634444670403359994 418 671185222629662565 419 710007611888471141 420 751027270501152117 421 794365893225217597 422 840151771940562030 423 888520144429357565 424 939613561802004877 425 993582277217921347 426 1050584652526698514 427 1110787585243079629 428 1174366961352848715 429 1241508127720865593 430 1312406389525416625 431 1387267535868930429 432 1466308390000239006 433 1549757386910698262 434 1637855184896074116 435 1730855304419846050 436 1829024799914710946 437 1932644969896517876 438 2042012099439937731 439 2157438240387112042 440 2279252035992086969 441 2407799583103467382 442 2543445338207827249 443 2686573074443023393 444 2837586882394141918 445 2996912221912901549 446 3164997031976735339 447 3342312892358306950 448 3529356243386831494 449 3726649673579687048 450 3934743266293493743 451 4154216014777309991 452 4385677314095651910 453 4629768523146143901 454 4887164603873142523 455 5158575851025762089 456 5444749700867678318 457 5746472632037112160 458 6064572167326822179 459 6399918970234458910 460 6753429044884184067 461 7126066055155391997 462 7518843750535526274 463 7932828514394509579 464 8369142046202087457 465 8828964170978706552 466 9313535785713353209 467 9824161964877405015 468 10362215207662589119 469 10929138849262124509 470 11526450648522661758 471 12155746546175009089 472 12818704606095119206 473 13517089165353699534 474 14252755175077403132 475 15027652758971828632 476 15843832004817448728 477 16703447984098455654 478 17608766014387270013 479 18562167197434169815 480 19566154212770429198 481 20623357399055296536 482 21736541143904242509 483 22908610576841038708 484 24142618585390946324 485 25441773194087396011 486 26809445283805650205 487 28249176692913617000 488 29764688725095365493 489 31359891059874417807 490 33038891092030416974 491 34806003747829918858 492 36665761755942432463 493 38622926421437830161 494 40682498936330761163 495 42849732224914251833 496 45130143356463198855 497 47529526584728963783 498 50053966992425432000 499 52709854797601767299 500 55503900370016473163 501 58443149951847005239 502 61535002131858892758 503 64787225140165492690 504 68207974946863359302 505 71805814232664765865 506 75589732293090365484 507 79569165874397820204 508 83754021003830085434 509 88154695896017490089 510 92782104924590634274 511 97647703739515217304 512 102763515614374107969 513 108142159019901116576 514 113796876509943059621 515 119741565017379986795 516 125990807557952764335 517 132559906439790741548 518 139464918087224457061 519 146722689479890498449 520 154350896320557281435 521 162368083047415618374 522 170793704704673920360 523 179648170788821978716 524 188952891211827306675 525 198730324390171007691 526 209004027602597569250 527 219798709765153012220 528 231140286649720304942 529 243055938692439620206 530 255574171579128615409 531 268724879615936803153 532 282539412083576165188 533 297050642746946636842 534 312293042577411901079 535 328302755868282428873 536 345117679978495796317 537 362777548735617597105 538 381324019742342147362 539 400800765806719811283 540 421253570587214776813 541 442730428674593949938 542 465281650416725902595 543 488959971533907567612 544 513820667841479368819 545 539921675355905573654 546 567323715916214434614 547 596090428608178480805 548 626288507373057185175 549 657987844885110167975 550 691261683100937680917 551 726186770826175451279 552 762843528495358672669 553 801316220524408628373 554 841693135723038327752 555 884066775899379174024 556 928534053163489565112 557 975196496376516473625 558 1024160467012798638935 559 1075537384895433787340 560 1129443964425832328271 561 1186002461498584714459 562 1245340931750955180185 563 1307593500717267933760 564 1372900646241339874260 565 1441409493763720808557 566 1513274125237032750439 567 1588655901979568574903 568 1667723802265625449281 569 1750654774393886881253 570 1837634105718071479818 571 1928855808417749751812 572 2024523022972619910831 573 2124848439775756528631 574 2230054739893179974566 575 2340375055932661696424 576 2456053453647803194835 577 2577345435309125250848 578 2704518466029068497917 579 2837852523671117836368 580 2977640673605376827301 581 3124189669549395315267 582 3277820581333612877548 583 3438869450915261913181 584 3607687978130533951548 585 3784644237072852078212 586 3970123424673560344946 587 4164528643091858825610 588 4368281717010420687815 589 4581824047550706828050 590 4805617504690736388312 591 5040145359382259097752 592 5285913257372563406576 593 5543450236786537658996 594 5813309790917592134924 595 6096070978439661841835 596 6392339583388038534926 597 6702749326578255474274 598 7027963130944330950502 599 7368674443471106805745 600 7725608615608304724697 601 8099524345008968947079 602 8491215181571859651094 603 8901511099998464202726 604 9331280142023343219347 605 9781430131746575331847 606 10252910466524401355107 607 10746713987093437530021 608 11263878930660742682419 609 11805490969929428366066 610 12372685342060094023280 611 12966649071929233957217 612 13588623292930640650577 613 14239905670003174130253 614 14921852929623506920944 615 15635883500689708397038 616 16383480271343079932564 617 17166193467340894406328 618 17985643656188818979056 619 18843524883026812726214 620 19741607944281202671540 621 20681743804230980698541 622 21665867160919106933704 623 22696000168534918535540 624 23774256321770796278914 625 24902844509821141303516 626 26084073247622123798377 627 27320355091091650743812 628 28614211244508674334577 629 29968276369136746270347 630 31385303600258805828211 631 32868169782346776944459 632 34419880932099931381701 633 36043577938048461605619 634 37742542507168659393036 635 39520203370023911638260 636 41380142753766300939557 637 43326103135393890761960 638 45361994287596548086373 639 47491900628495537959512 640 49720088888567268135515 641 52051016109337598821468 642 54489337986048548269192 643 57039917569931420834197 644 59707834345864848831583 645 62498393699977533217919 646 65417136794129832978036 647 68469850865780113327965 648 71662579969019580862358 649 75001636176638139944698 650 78493611263320164539767 651 82145388888643043470799 652 85964157301536600293495 653 89957422589569833717200 654 94133022493548968724775 655 98499140812558803898704 656 103064322425023211792342 657 107837488949809989065929 658 112827955074913002334050 659 118045445583304154484705 660 123500113102425204602826 661 129202556609097047828710 662 135163840722464372438561 663 141395515815671077961853 664 147909638981369138309281 665 154718795888509807216305 666 161836123564467867341558 667 169275334142778979220226 668 177050739617934961855971 669 185177277646464920007000 670 193670538439075781614083 671 202546792791040806401240 672 211823021294790784303702 673 221516944785513598520827 674 231647056072522032416546 675 242232653006487639000773 676 253293872939372299146984 677 264851728636823004821860 678 276928145699326166427395 679 289546001556420690630406 680 302729166100966018543995 681 316502544027298349114063 682 330892118945569487726851 683 345924999347641064484017 684 361629466496738978365767 685 378035024322124661694535 686 395172451403719763986534 687 413073855128097716805852 688 431772728107462894273539 689 451304006956887513875970 690 471704133522123754431798 691 493011118660578088588461 692 515264608683217587126383 693 538505954560882476468605 694 562778284011209428744931 695 588126576586494237753848 696 614597741880182239682752 697 642240700981698994131819 698 671106471315966447204890 699 701248254999186429535522 700 732721530858088486623287 701 765584150264383983283817 702 799896436934556053923498 703 835721290858566323633164 704 873124296530010565793748 705 912173835645002494393754 706 952941204455582920324722 707 995500735969642748420800 708 1039929927187815424526017 709 1086309571584142113450149 710 1134723897048374723370258 711 1185260709502125109616516 712 1238011542423849366244124 713 1293071812524626739545249 714 1350540981816637310715739 715 1410522726335377896382408 716 1473125111790405043120792 717 1538460776413972484337579 718 1606647121303779790877253 719 1677806508565323425240570 720 1752066467560350728370175 721 1829559909590627157411320 722 1910425351363657870745500 723 1994807147581499591738649 724 2082855733026179467057329 725 2174727874526992631684641 726 2270586933197330816720543 727 2370603137356511367828258 728 2474953866572979243070499 729 2583823947260838205464513 730 2697405960300205878362973 731 2815900561166784771842801 732 2939516813060910221387746 733 3068472533559375734579884 734 3202994655339401985258819 735 3343319601521124269630591 736 3489693676220477435622015 737 3642373470924161226796960 738 3801626287305311335233717 739 3967730577139094403038923 740 4140976400009417404539072 741 4321665899496460320659026 742 4510113798589850480720310 743 4706647915097260493578170 744 4911609697828382541168009 745 5125354784384501804388702 746 5348253581421568330137790 747 5580691868258122005702766 748 5823071424763356106964871 749 6075810684493833795619892 750 6339345414061661326827785 751 6614129419777886303163128 752 6900635282661697240736118 753 7199355122913462684542931 754 7510801395026332203757712 755 7835507714754047254516183 756 8174029719171448877486531 757 8526945961140026239793792 758 8894858839546735133665575 759 9278395566699442526223996 760 9678209174353240451256466 761 10094979559896657468905976 762 10529414574253016707469243 763 10982251153144866720267566 764 11454256493437595775452820 765 11946229276303094845246103 766 12459000939051707949371481 767 12993436997552395045223805 768 13550438421194486552552411 769 14130943062459115708348673 770 14735927143251599193618325 771 15366406800182728357590379 772 16023439691115914702712123 773 16708126665387473721791582 774 17421613500152185815930622 775 18165092705448165048335135 776 18939805400674688060287320 777 19747043265231758505663822 778 20588150566222330142532798 779 21464526266234739588277869 780 22377626214281023036818072 781 23328965423140523190012375 782 24320120436482244634533788 783 25352731789213158442499373 784 26428506564684784190905906 785 27549221052536075120023247 786 28716723511027177879983958 787 29932937037933160866071865 788 31199862554217234001347445 789 32519581904805012637122034 790 33894261081003461865730996 791 35326153569291332110820311 792 36817603831309475458719230 793 38371050920140288560046302 794 39989032238152666267924728 795 41674187441824640440155821 796 43429262499223365761478566 797 45257113906052838839358458 798 47160713066311153967482070 799 49143150843919479017546161 800 51207642291916324690718417 801 53357531565987506876175879 802 55596297029429164327161614 803 57927556556927000319093230 804 60355073044707470008978978 805 62882760135008012013842513 806 65514688163099350277655822 807 68255090335325018826480035 808 71108369147018706878807651 809 74079103049516690371101360 810 77172053375707586820145310 811 80392171534037615075318184 812 83744606481247587742748819 813 87234712484413634351287497 814 90868057183348354765049734 815 94650429964861758920044870 816 98587850660670507299136186 817 102686578581328103311565597 818 106953121898990008302046342 819 111394247392210165189539098 820 116016990566555816932442643 821 120828666165374549183917343 822 125836879085425384982182838 823 131049535712791439349896429 824 136474855695048467182709446 825 142121384166144328057782745 826 147998004441170196953438252 827 154113951198881243727140926 828 160478824170308101500767099 829 167102602352663399186387554 830 173995658768439543118835887 831 181168775790202562625287263 832 188633161052479346851204346 833 196400463972967198272933428 834 204482792905919042042841277 835 212892732951607036331330096 836 221643364446629269129125715 837 230748282160593528518919762 838 240221615225805859855817407 839 250078047827618765241768308 840 260332840683892912349622861 841 271001853343300701818922487 842 282101567333279995665326152 843 293649110189407130991550334 844 305662280399307534328717323 845 318159573295485249245248610 846 331160207932470138754794611 847 344684154985237551725996244 848 358752165707196047633926978 849 373385801987246377308024712 850 388607467547073681934240398 851 404440440321386832002885808 852 420908906065118192162847029 853 438037993233483752384306478 854 455853809182481442438703340 855 474383477738910299809395458 856 493655178191035197158997909 857 513698185752933322967279041 858 534542913557200534729311201 859 556220956232998832998062358 860 578765135128512013300048433 861 602209545238751868789340924 862 626589603902176042014369848 863 651942101331923833894854651 864 678305253049552808911257166 865 705718754291968993868670585 866 734223836464829266280993999 867 763863325718040419630944377 868 794681703722068651195040497 869 826725170726664733640849441 870 860041710986224044276413414 871 894681160639423515025322411 872 930695278133994468375178566 873 968137817290403831297276307 874 1007064603102019341926644181 875 1047533610372891520359725673 876 1089605045297562047404866717 877 1133341430091495830559703704 878 1178807690784710863288557571 879 1226071248294812125363017142 880 1275202112900306970409565546 881 1326272982239453164202389684 882 1379359342964001407164643341 883 1434539576182301553349758171 884 1491895066831169519446705799 885 1551510317120427572306407722 886 1613473064199760329833504035 887 1677874402202922987995835972 888 1744808908829458865382548975 889 1814374776630339519787477638 890 1886673949170025182062247576 891 1961812262243051451498980070 892 2039899590330287140837865604 893 2121049998486637864078670779 894 2205381899858361177823328147 895 2293018219035805505104765783 896 2384086561454895186373998151 897 2478719389067654272332664427 898 2577054202510684284004136058 899 2679233730008679866204996861 900 2785406123258011424081291964 901 2895725160544758733082422498 902 3010350457360849134181644515 903 3129447684790586955486063547 904 3253188795950439862732433277 905 3381752260775006488904089628 906 3515323309451932848528026578 907 3654094184820024877763413694 908 3798264404056194372687134850 909 3948041029987599631048174127 910 4103638952378292125694643024 911 4265281179552054612353157135 912 4433199140725330998677039656 913 4607632999438185879260584206 914 4788831978485262229813197494 915 4977054696761985885271249397 916 5172569518457110596620680719 917 5375654915037947398688020587 918 5586599840489707903046717181 919 5805704120287605045099164857 920 6033278854597594500945017540 921 6269646836218075871547032777 922 6515142983794274445372992518 923 6770114790855769535453857535 924 7034922791246284738270935264 925 7309941041535944644572297182 926 7595557621027363849750793908 927 7892175149987280472792690285 928 8200211326759156531920173180 929 8520099484435245357860519726 930 8852289167789622704471519705 931 9197246731199508219591837039 932 9555455958308193170444247516 933 9927418704208016146364144333 934 10313655560950828294318091381 935 10714706547221762476242544441 936 11131131823040446802972003045 937 11563512430385472298061260203 938 12012451060669764654256475183 939 12478572850025558463987287463 940 12962526203393105642219084841 941 13464983648442115491668291257 942 13986642720389808461332339954 943 14528226878818230315841553961 944 15090486457632514352490339875 945 15674199649340090030730863412 946 16280173524874096299762501633 947 16909245090227123414345623717 948 17562282381204278049418164382 949 18240185597652044888424593826 950 18943888278567259077544730359 951 19674358519537677614630201719 952 20432600234018529292004364099 953 21219654460002001376351302502 954 22036600713689328992785822977 955 22884558391833264597669329048 956 23764688224477256883336766846 957 24678193779875802330304627311 958 25626323023444969904306434736 959 26610369932656633959853991290 960 27631676169854671031779959101 961 28691632815042457197824211494 962 29791682160762696600567958704 963 30933319571262081456983090863 964 32118095408212107175145076300 965 33347617025336484671124299334 966 34623550834374989945677089624 967 35947624444900545553602123439 968 37321628880594012723060768053 969 38747420874669028906924951539 970 40226925247235433381852355913 971 41762137367486733856880080167 972 43355125703694480187202475531 973 45008034464098657896377085865 974 46723086331890469574863295781 975 48502585297591744880781425133 976 50348919592252591624428132583 977 52264564725007617011256973527 978 54252086628650374992363617720 979 56314144917015531614209264908 980 58453496258089359289073967747 981 60672997866901472581616944123 982 62975611122393964481889097638 983 65364405312609301711696824965 984 67842561512684535053007916362 985 70413376600297936993484658422 986 73080267413374347463221567597 987 75846775055017741090494764088 988 78716569350814173521193175300 989 81693453463825881865196360981 990 84781368672776248917474449792 991 87984399319118830660869658283 992 91306777928879369941370958005 993 94752890515358301607428526314 994 98327282068994299846820762704 995 102034662240906422414893309844 996 105879911226851315241353110586 997 109868085858568032585527450346 998 114004425909721931667543471911 999 118294360623902162531179843953 1000 122743515472386962786998080157