0 1 1 5 2 15 3 39 4 90 5 189 6 375 7 707 8 1276 9 2226 10 3768 11 6210 12 10002 13 15780 14 24432 15 37198 16 55772 17 82443 18 120300 19 173445 20 247284 21 348916 22 487555 23 675088 24 926784 25 1262091 26 1705644 27 2288518 28 3049654 29 4037611 30 5312713 31 6949490 32 9039627 33 11695524 34 15054338 35 19282807 36 24582982 37 31198732 38 39423421 39 49608912 40 62175780 41 77625228 42 96552926 43 119664678 44 147794521 45 181925587 46 223213631 47 273014001 48 332912512 49 404760126 50 490712459 51 593274691 52 715351843 53 860305720 54 1032019237 55 1234968220 56 1474302256 57 1755935549 58 2086648017 59 2474198539 60 2927451640 61 3456517978 62 4072911013 63 4789721516 64 5621810468 65 6586023323 66 7701427684 67 8989575256 68 10474791724 69 12184497092 70 14149557776 71 16404674837 72 18988811549 73 21945662103 74 25324166707 75 29179077110 76 33571574912 77 38569949021 78 44250337256 79 50697535145 80 58005879626 81 66280213718 82 75636936140 83 86205145133 84 98127883806 85 111563492176 86 126687076856 87 143692107299 88 162792145154 89 184222719659 90 208243359915 91 235139792130 92 265226317167 93 298848381446 94 336385351118 95 378253507694 96 424909280628 97 476852729067 98 534631294164 99 598843840314 100 670145000281 101 749249849183 102 836938929138 103 934063642692 104 1041552044103 105 1160415054313 106 1291753121276 107 1436763359541 108 1596747199494 109 1773118572042 110 1967412668211 111 2181295309168 112 2416572957337 113 2675203414363 114 2959307247261 115 3271179979131 116 3613305097161 117 3988367926051 118 4399270409722 119 4849146861901 120 5341380741544 121 5879622503186 122 6467808591873 123 7110181647430 124 7811311976377 125 8576120371471 126 9409902353366 127 10318353902244 128 11307598770901 129 12384217464769 130 13555277967634 131 14828368317238 132 16211631128825 133 17713800157592 134 19344239018474 135 21112982175542 136 23030778305514 137 25109136169933 138 27360373124108 139 29797666382549 140 32435107193528 141 35287758068339 142 38371713202274 143 41704162259969 144 45303457690193 145 49189185726542 146 53382241268723 147 57904906831428 148 62780935738864 149 68035639784051 150 73695981564390 151 79790671695379 152 86350271148881 153 93407298954522 154 100996345492542 155 109154191654833 156 117919934142447 157 127335117157506 158 137443870799601 159 148293056467791 160 159932419559082 161 172414749809931 162 185796049618417 163 200135710674227 164 215496699283131 165 231945750763993 166 249553573285181 167 268395061571463 168 288549520903720 169 310100901822112 170 333138046012666 171 357754943847961 172 384051004041004 173 412131335945671 174 442107045027439 175 474095542016860 176 508220866337293 177 544614024389045 178 583413343260726 179 624764840522884 180 668822610750146 181 715749229406244 182 765716174816680 183 818904268945109 184 875504137677320 185 935716691413736 186 999753626762369 187 1067837950112351 188 1140204523971749 189 1217100636944235 190 1298786598208090 191 1385536357470905 192 1477638151364871 193 1575395177236744 194 1679126295403241 195 1789166760935169 196 1905868986022515 197 2029603334097366 198 2160758946884610 199 2299744605539286 200 2446989627162699 201 2602944797982501 202 2768083344471774 203 2942901943823805 204 3127921775192647 205 3323689613100635 206 3530778964563891 207 3749791251481519 208 3981357039826016 209 4226137317331149 210 4484824821369815 211 4758145418706483 212 5046859538977690 213 5351763663751471 214 5673691873009249 215 6013517451073471 216 6372154554002309 217 6750559940466950 218 7149734768317559 219 7570726459042955 220 8014630632325266 221 8482593113091979 222 8975812013468771 223 9495539892034289 224 10043085992990465 225 10619818567865466 226 11227167282365095 227 11866625711213711 228 12539753923831283 229 13248181163693216 230 13993608624458603 231 14777812325959495 232 15602646093146393 233 16470044641337781 234 17382026771130297 235 18340698676331872 236 19348257368546171 237 20406994222048621 238 21519298642602580 239 22687661864144524 240 23914680877282783 241 25203062493564578 242 26555627549762532 243 27975315256450636 244 29465187695152354 245 31028434468657054 246 32668377509122364 247 34388476048596615 248 36192331756926049 249 38083694052036013 250 40066465587596407 251 42144707923429063 252 44322647384043843 253 46604681110715293 254 48995383312876976 255 51499511724644999 256 54122014272310674 257 56868035959027438 258 59742925972956333 259 62752245025166688 260 65901772923995007 261 69197516392608357 262 72645717136556473 263 76252860168524285 264 80025682397544603 265 83971181489975019 266 88096625009991513 267 92409559847405812 268 96917821940663678 269 101629546303351902 270 106553177362603696 271 111697479617847452 272 117071548628838990 273 122684822341986077 274 128547092764035228 275 134668517992711864 276 141059634613979707 277 147731370475654357 278 154695057847652956 279 161962446979243631 280 169545720063736160 281 177457505621628164 282 185710893313311824 283 194319449192532048 284 203297231412387178 285 212658806395763886 286 222419265482191432 287 232594242063730508 288 243199929222621855 289 254253097883521798 290 265771115493813434 291 277771965245600958 292 290274265853107137 293 303297291899887203 294 316860994770400852 295 330986024180608286 296 345693750322981122 297 361006286641459360 298 376946513252021057 299 393538101025289478 300 410805536347756019 301 428774146578343182 302 447470126217826312 303 466920563808798931 304 487153469584024111 305 508197803881846930 306 530083506347521169 307 552841525939475144 308 576503851760412443 309 601103544733334648 310 626674770142760211 311 653252831062322932 312 680874202690140558 313 709576567613545960 314 739398852025722968 315 770381262917013055 316 802565326263875358 317 835993926239475812 318 870711345470121897 319 906763306361991417 320 944197013523642795 321 983061197310051217 322 1023406158514165207 323 1065283814233063423 324 1108747744936065724 325 1153853242762422662 326 1200657361077339117 327 1249218965315382344 328 1299598785140614296 329 1351859467953968098 330 1406065633778705048 331 1462283931555097041 332 1520583096876711592 333 1581034011201014693 334 1643709762567335648 335 1708685707856525075 336 1776039536626996323 337 1845851336562193078 338 1918203660565868108 339 1993181595541939767 340 2070872832896070760 341 2151367740797511302 342 2234759438240156425 343 2321143870942170002 344 2410619889124983708 345 2503289327212914484 346 2599257085495071422 347 2698631213792740902 348 2801522997175901551 349 2908047043772974291 350 3018321374719495606 351 3132467516291891984 352 3250610594273017014 353 3372879430597761052 354 3499406642327562128 355 3630328743003162105 356 3765786246426666682 357 3905923772924519130 358 4050890158143544651 359 4200838564434005744 360 4355926594874194953 361 4516316409991669708 362 4682174847238091084 363 4853673543275248857 364 5030989059130466859 365 5214303008281516593 366 5403802187731821844 367 5599678712137385945 368 5802130151048884938 369 6011359669333060984 370 6227576170838238986 371 6450994445370879213 372 6681835319050810394 373 6920325808113515874 374 7166699276230016737 375 7421195595415670489 376 7684061310599971305 377 7955549807931695980 378 8235921486894557277 379 8525443936309335514 380 8824392114300807668 381 9133048532308653588 382 9451703443222374250 383 9780655033722696692 384 10120209620912845890 385 10470681853323967947 386 10832394916381520964 387 11205680742420405457 388 11590880225337559148 389 11988343439973368880 390 12398429866314260539 391 12821508618609829715 392 13257958679500605438 393 13708169139253600304 394 14172539440203853692 395 14651479626503010082 396 15145410599277088340 397 15654764377296707700 398 16179984363265978510 399 16721525615837435304 400 17279855127461559250 401 17855452108182487508 402 18448808275492737366 403 19060428150361002370 404 19690829359550240360 405 20340542944344567760 406 21010113675804763739 407 21700100376675469341 408 22411076250068525464 409 23143629215048245916 410 23898362249247826515 411 24675893738647514530 412 25476857834646583795 413 26301904818564690274 414 27151701473709674102 415 28026931465150367250 416 28928295727336621636 417 29856512859710337410 418 30812319530452836780 419 31796470888517715325 420 32809740984099944839 421 33852923197693640388 422 34926830677894828826 423 36032296788107275896 424 37170175562311144240 425 38341342170058322165 426 39546693390860061220 427 40787148098134358449 428 42063647752884731644 429 43377156907283916112 430 44728663718337895871 431 46119180471810041400 432 47549744116587094580 433 49021416809670713250 434 50535286471982798824 435 52092467355174891465 436 53694100619633977058 437 55341354923881720981 438 57035427025566298085 439 58777542394248140015 440 60568955836185757160 441 62410952131330040944 442 64304846682737702786 443 66251986178619509784 444 68253749267241323886 445 70311547244898305275 446 72426824757187814150 447 74601060513808997210 448 76835768017119503379 449 79132496304685122367 450 81492830706060701771 451 83918393614043261911 452 86410845270643760925 453 88971884568026635844 454 91603249864668918785 455 94306719816996451118 456 97084114226757503928 457 99937294904396903893 458 102868166548699680512 459 105878677642976153136 460 108970821368063289418 461 112146636532423279400 462 115408208519623296716 463 118757670253483455394 464 122197203181186285479 465 125729038274644207969 466 129355457050424651702 467 133078792608538981188 468 136901430690404693240 469 140825810756293632614 470 144854427082585721864 471 148989829879151122424 472 153234626427187174851 473 157591482237843432928 474 162063122231971666434 475 166652331941341282591 476 171361958731667807708 477 176194913047805777659 478 181154169681461106993 479 186242769061785429917 480 191463818569218766378 481 196820493872950735250 482 202316040292378202517 483 207953774182941266993 484 213737084346723508455 485 219669433468210338967 486 225754359575603469383 487 231995477528093688057 488 238396480529502318316 489 244961141668706055162 490 251693315487264235609 491 258596939574676023941 492 265676036191699499157 493 272934713922169156954 494 280377169353757030751 495 288007688788127320822 496 295830649980939119066 497 303850523912160785655 498 312071876587164399436 499 320499370869073582238 500 329137768342847251020 501 337991931211586900816 502 347066824225560089538 503 356367516644442338860 504 365899184233284904476 505 375667111292721134120 506 385676692723933968379 507 395933436128912578875 508 406442963946531603172 509 417211015624996574609 510 428243449831204792675 511 439546246697576546537 512 451125510106922057949 513 462987470015915367850 514 475138484817752267504 515 487585043744580152763 516 500333769310293751574 517 513391419794296772061 518 526764891766840625083 519 540461222656557667859 520 554487593360812740876 521 568851330899508210583 522 583559911112984255589 523 598620961404662691328 524 614042263529094411917 525 629831756426077293679 526 645997539101518197000 527 662547873555724843907 528 679491187759820358532 529 696836078680980292895 530 714591315357204468351 531 732765842022343220363 532 751368781282104924549 533 770409437341784562727 534 789897299286460600868 535 809842044414415004922 536 830253541624544479651 537 851141854858538797059 538 872517246598609902784 539 894390181421569136903 540 916771329610057964470 541 939671570821745704338 542 963101997817321796633 543 987073920248118489616 544 1011598868504208200333 545 1036688597623834270389 546 1062355091265042463982 547 1088610565740389222748 548 1115467474115617580233 549 1142938510373200559435 550 1171036613641660847661 551 1199774972491590858793 552 1229167029299306522193 553 1259226484679077416076 554 1289967301984891618445 555 1321403711882723196208 556 1353550216994279844057 557 1386421596613224395411 558 1420032911494873798384 559 1454399508720389063147 560 1489537026636486365490 561 1525461399871709690081 562 1562188864430315647068 563 1599735962864838249004 564 1638119549528411972141 565 1677356795907942023631 566 1717465196039228371636 567 1758462572005160985475 568 1800367079518114683186 569 1843197213587690114213 570 1886971814274958659175 571 1931710072534380336951 572 1977431536144582451873 573 2024156115729198337840 574 2071904090868977233381 575 2120696116306395490171 576 2170553228244011316749 577 2221496850737817321060 578 2273548802186864817871 579 2326731301920446252954 580 2381066976884134554294 581 2436578868425998464877 582 2493290439184325700316 583 2551225580078198635431 584 2610408617402288024165 585 2670864320027243460907 586 2732617906707072560694 587 2795695053494922210953 588 2860121901268688872382 589 2925925063367898596826 590 2993131633343319394828 591 3061769192820782638175 592 3131865819480704310909 593 3203450095154819485699 594 3276551114041657895493 595 3351198491042303049181 596 3427422370218000511211 597 3505253433371195915929 598 3584722908751598323935 599 3665862579888888322091 600 3748704794553705690730 601 3833282473848566962949 602 3919629121430387638605 603 4007778832866299716091 604 4097766305124471184404 605 4189626846201659215354 606 4283396384889245182097 607 4379111480679516106161 608 4476809333813982902251 609 4576527795475542676015 610 4678305378126309316797 611 4782181265992963074314 612 4888195325701487212723 613 4996388117063177341212 614 5106800904013836163646 615 5219475665708084327678 616 5334455107770736086075 617 5451782673707216345074 618 5571502556475014154029 619 5693659710218186264373 620 5818299862166952984241 621 5945469524704447584411 622 6075216007602699646564 623 6207587430429962090525 624 6342632735131511211631 625 6480401698786068771705 626 6620944946540025291449 627 6764313964721663872330 628 6910561114137604174331 629 7059739643553717057279 630 7211903703362781175350 631 7367108359441173707822 632 7525409607196919091166 633 7686864385811441010545 634 7851530592677384413530 635 8019467098034906810611 636 8190733759808860140709 637 8365391438649306617465 638 8543502013177845306213 639 8725128395442248832307 640 8910334546581932408886 641 9099185492706811551185 642 9291747340992128154641 643 9488087295991848061584 644 9688273676173268284885 645 9892375930675496044074 646 10100464656294485887223 647 10312611614697357105712 648 10528889749868738323725 649 10749373205791910949886 650 10974137344367560023374 651 11203258763572966359665 652 11436815315864499418015 653 11674886126826308082519 654 11917551614068132637653 655 12164893506375187466075 656 12416994863113102704801 657 12673940093890939925409 658 12935814978485323891960 659 13202706687028772118941 660 13474703800465331540475 661 13751896331276659342784 662 14034375744481725668365 663 14322234978913344260491 664 14615568468774765629399 665 14914472165479608988200 666 15219043559778438349997 667 15529381704175317487681 668 15845587235637721150035 669 16167762398603209874285 670 16496011068286305862551 671 16830438774289051122739 672 17171152724518759849825 673 17518261829416507981038 674 17871876726499947655652 675 18232109805224065935202 676 18599075232163538940570 677 18972888976520378453306 678 19353668835960600516698 679 19741534462783678236555 680 20136607390428587990803 681 20539011060320291621393 682 20948870849060530737669 683 21366314095966857404461 684 21791470130963859750267 685 22224470302830575499757 686 22665448007808135730655 687 23114538718571716343032 688 23571880013570910125214 689 24037611606742682773310 690 24511875377601112357748 691 24994815401708148067918 692 25486577981529675747762 693 25987311677681214834495 694 26497167340567608614771 695 27016298142421122629479 696 27544859609742404135535 697 28083009656148793829005 698 28630908615634535204249 699 29188719276247466002273 700 29756606914186815514901 701 30334739328326786953926 702 30923286875170644204254 703 31522422504240062626744 704 32132321793904560318426 705 32753162987655867403374 706 33385127030832132323444 707 34028397607796922173497 708 34683161179578016363527 709 35349607021971035359825 710 36027927264113005694603 711 36718316927531005759927 712 37420973965671080476883 713 38136099303912673750365 714 38863896880073872060097 715 39604573685412797244874 716 40358339806130548758846 717 41125408465381141265178 718 41905996065793929287498 719 42700322232514074293092 720 43508609856766656341191 721 44331085139950079450856 722 45167977638264484964996 723 46019520307880935137196 724 46885949550657177382049 725 47767505260405866250794 726 48664430869721169353042 727 49576973397369732886362 728 50505383496252050577565 729 51449915501940330234948 730 52410827481799002806480 731 53388381284694088524220 732 54382842591297686381944 733 55394480964993905162538 734 56423569903392625492058 735 57470386890457535363765 736 58535213449254934838395 737 59618335195329878501364 738 60720041890716278543621 739 61840627498587645918078 740 62980390238555221544959 741 64139632642620305165133 742 65318661611787645384286 743 66517788473346830643392 744 67737329038828677845914 745 68977603662643672704717 746 70238937301409593759712 747 71521659573975510418760 748 72826104822149404116892 749 74152612172136741306282 750 75501525596697386828544 751 76873193978028306394565 752 78267971171379588285778 753 79686216069411375689301 754 81128292667299362715271 755 82594570128596590340240 756 84085422851859341300183 757 85601230538044996094110 758 87142378258689797287707 759 88709256524874533599364 760 90302261356986219922426 761 91921794355283936325162 762 93568262771277054916278 763 95242079579924149692259 764 96943663552660973266520 765 98673439331265951813280 766 100431837502571717367894 767 102219294674031287349872 768 104036253550147570218127 769 105883163009774945590967 770 107760478184301759866484 771 109668660536722649056905 772 111608177941609671629333 773 113579504765991328855594 774 115583121951148622520939 775 117619517095337372611052 776 119689184537446114343062 777 121792625441598967965068 778 123930347882712949234690 779 126102866933019287308560 780 128310704749558392581219 781 130554390662658193239691 782 132834461265405660244272 783 135151460504121418026543 784 137505939769847416201297 785 139898457990857740697165 786 142329581726202722091256 787 144799885260296578761534 788 147309950698558937773418 789 149860368064120657634782 790 152451735395604458742470 791 155084658845990974871796 792 157759752782580922161336 793 160477639888064165622236 794 163238951262706572997444 795 166044326527665630818859 796 168894413929445883003047 797 171789870445505364441262 798 174731361891024289012055 799 177719563026847338892333 800 180755157668611016520276 801 183838838797067609514740 802 186971308669617408306124 803 190153278933060933107007 804 193385470737583017820848 805 196668614851980689980459 806 200003451780146905110935 807 203390731878822286949266 808 206831215476627118519437 809 210325672994385950839604 810 213874885066757291184428 811 217479642665180928495823 812 221140747222155577842048 813 224859010756859623111596 814 228635256002127834943856 815 232470316532797067780914 816 236365036895434039382574 817 240320272739458396158565 818 244336890949674397166228 819 248415769780224651293603 820 252557798989979444399716 821 256763879979375325326396 822 261034925928716723633765 823 265371861937954476436039 824 269775625167955276553262 825 274247164983276160443214 826 278787443096458261207569 827 283397433713854189559771 828 288078123683003514234916 829 292830512641570922502120 830 297655613167861781837633 831 302554450932929934787748 832 307528064854292670635715 833 312577507251267960727786 834 317703844001949157708482 835 322908154701832472951732 836 328191532824112692597940 837 333555085881662708481832 838 338999935590712556759193 839 344527218036243806098280 840 350138083839115255703793 841 355833698324936022487128 842 361615241694702248749869 843 367483909197213782713280 844 373440911303287305843147 845 379487473881782536021417 846 385624838377458259182400 847 391854261990675066276479 848 398177017858961830617384 849 404594395240463086885066 850 411107699699284599979911 851 417718253292754573250483 852 424427394760618074541836 853 431236479716182388152085 854 438146880839431165299649 855 445159988072125377388510 856 452277208814909208754912 857 459499968126439193347267 858 466829708924555034275344 859 474267892189510680367811 860 481815997169284404956250 861 489475521586986769426914 862 497247981850385492153381 863 505134913263566417858008 864 513137870240749922664888 865 521258426522282231101115 866 529498175392821299139076 867 537858729901737060542165 868 546341723085745977733789 869 554948808193800019705617 870 563681658914250335659964 871 572541969604306040043859 872 581531455521808709457891 873 590651853059343341153496 874 599904919980706672855450 875 609292435659753952061834 876 618816201321645395298958 877 628478040286513730957835 878 638279798215574411392820 879 648223343359700235439262 880 658310566810482278839021 881 668543382753799225804320 882 678923728725917353644514 883 689453565872143581940069 884 700134879208054197239761 885 710969677883322026227411 886 721959995448164993136903 887 733107890122439200509491 888 744415445067399837679790 889 755884768660153387540659 890 767517994770824809340815 891 779317283042463543929502 892 791284819173712357427627 893 803422815204263250448804 894 815733509803124832082426 895 828219168559725730878195 896 840882084277878830208254 897 853724577272631290971391 898 866748995670025501141198 899 879957715709796310856238 900 893353142051030090900376 901 906937708080811332517346 902 920713876225882729837330 903 934684138267344868954228 904 948851015658421831409727 905 963217059845319247380113 906 977784852591201520283234 907 992557006303315131936088 908 1007536164363285169195152 909 1022725001460612403157916 910 1038126223929398443177397 911 1053742570088326724061313 912 1069576810583927278774297 913 1085631748737153443946810 914 1101910220893298886003509 915 1118415096775283533537019 916 1135149279840337200402577 917 1152115707640109928989637 918 1169317352184238284859329 919 1186757220307397036717201 920 1204438354039865905215970 921 1222363830981641269788814 922 1240536764680122929503851 923 1258960305011406268060238 924 1277637638565210382793288 925 1296571989033472948424941 926 1315766617602642845090241 927 1335224823349701794038875 928 1354949943641946459414038 929 1374945354540562738045027 930 1395214471208024177250463 931 1415760748319346679842264 932 1436587680477231923882033 933 1457698802631132147050732 934 1479097690500269168947096 935 1500787961000640797896782 936 1522773272676047995469388 937 1545057326133176399699927 938 1567643864480766086246440 939 1590536673772903677709489 940 1613739583456471143556884 941 1637256466822785916365077 942 1661091241463467185546617 943 1685247869730563466428209 944 1709730359200976830925151 945 1734542763145219426054561 946 1759689181000538147762704 947 1785173758848443631128356 948 1811000689896679962600382 949 1837174214965671765774153 950 1863698622979485611085710 951 1890578251461342949059986 952 1917817487033722017297462 953 1945420765923086475613879 954 1973392574469278777743413 955 2001737449639616543343566 956 2030459979547730503694929 957 2059564803977182853313055 958 2089056614909905099861122 959 2118940157059494819916283 960 2149220228409410991874890 961 2179901680756107842360895 962 2210989420257147463273005 963 2242488407984331725311785 964 2274403660481894283895169 965 2306740250329793799836623 966 2339503306712149770904643 967 2372698015990862645531347 968 2406329622284460222170667 969 2440403428052212616672195 970 2474924794683558360350551 971 2509899143092884529503033 972 2545331954319704091210349 973 2581228770134273935801632 974 2617595193648697410368159 975 2654436889933555457093174 976 2691759586640110751012981 977 2729569074628129581861167 978 2767871208599366519401262 979 2806671907736757197887965 980 2845977156349364911459480 981 2885793004523127012457891 982 2926125568777447406395035 983 2966981032727681799646913 984 3008365647753562661682253 985 3050285733673611170924997 986 3092747679425583781997441 987 3135757943753001363441973 988 3179323055897809167960073 989 3223449616299216272230675 990 3268144297298763440439691 991 3313413843851668684313143 992 3359265074244500173955053 993 3405704880819226476653906 994 3452740230703694425292577 995 3500378166548585306088694 996 3548625807270900384122865 997 3597490348804027115498219 998 3646979064854437789732498 999 3697099307665072680674635 1000 3747858508785460120632186