0 1 1 3 2 9 3 33 4 93 5 242 6 568 7 1237 8 2532 9 4905 10 9071 11 16113 12 27654 13 45997 14 74388 15 117408 16 181271 17 274163 18 407066 19 594568 20 855087 21 1211979 22 1695785 23 2344564 24 3204123 25 4332497 26 5802690 27 7699864 28 10126446 29 13212343 30 17109772 31 21991217 32 28071644 33 35611707 34 44895662 35 56258904 36 70122970 37 86952326 38 107252879 39 131662888 40 160926827 41 195806222 42 237211826 43 286283570 44 344189785 45 412185262 46 491903413 47 585147630 48 693659045 49 819621970 50 965728510 51 1134509009 52 1328744110 53 1552186521 54 1808659603 55 2101709820 56 2436150619 57 2817672954 58 3251127265 59 3742249148 60 4298947443 61 4928435606 62 5637392875 63 6435788331 64 7334516422 65 8341990431 66 9469551037 67 10732633266 68 12143446648 69 13714053400 70 15464049215 71 17412379106 72 19572581575 73 21966507822 74 24622099350 75 27557961965 76 30795686087 77 34371857563 78 38316296199 79 42649950185 80 47413987014 81 52655152487 82 58399055650 83 64684807467 84 71576992022 85 79117632656 86 87339491105 87 96317929362 88 106124605569 89 116791750044 90 128391161718 91 141029829289 92 154759575167 93 169634809457 94 185788155383 95 203318686232 96 222265238242 97 242759387536 98 264965810694 99 288937739559 100 314772700246 101 342692531416 102 372816972958 103 405196551847 104 440067018844 105 477660546842 106 518017039038 107 561319831414 108 607917816234 109 657928264124 110 711433873497 111 768840199398 112 830439805683 113 896243012361 114 966595097000 115 1042005979263 116 1122544981206 117 1208380420434 118 1300173212909 119 1398235872424 120 1502545812065 121 1613731719063 122 1732475051003 123 1858729903040 124 1992861384699 125 2135879343235 126 2288024025789 127 2449277990345 128 2620725937036 129 2803176740250 130 2996395233960 131 3201140689930 132 3418844709082 133 3649518213313 134 3893273024604 135 4151864466828 136 4426089291991 137 4715481216949 138 5021501184038 139 5346003692641 140 5688553461280 141 6049660046358 142 6431970823666 143 6835993502554 144 7261091631937 145 7709851205535 146 8184404640880 147 8683634123849 148 9208921297000 149 9763961210593 150 10348532535338 151 10962096391153 152 11608872134538 153 12290887917406 154 13006181657967 155 13757732235898 156 14550254294276 157 15382212220416 158 16253766840889 159 17171275624841 160 18135955329826 161 19145072967864 162 20204179751776 163 21318636224805 164 22484957756459 165 23705067039485 166 24987796056111 167 26332470572166 168 27736120236817 169 29208011475062 170 30753243135272 171 32365904832666 172 34051283849115 173 35820603918318 174 37669894472517 175 39597205283558 176 41616628985791 177 43731388455956 178 45933167773260 179 48232739851727 180 50642890049120 181 53154826082342 182 55769845381525 183 58507600391865 184 61367031711709 185 64338394049737 186 67440395881320 187 70685439666149 188 74058690434510 189 77568032600823 190 81238534344338 191 85061758465351 192 89028982956242 193 93169214774326 194 97491089458820 195 101973485589067 196 106635254789369 197 111505229393896 198 116564216855129 199 121808915746724 200 127280225817858 201 132978040292818 202 138876574764499 203 145010673403408 204 151409090860430 205 158039033917047 206 164909214434517 207 172072302250367 208 179513081154567 209 187205583307461 210 195205502149192 211 203534892510363 212 212146313581073 213 221069116353332 214 230364744366704 215 239995865226685 216 249944534484727 217 260290702599433 218 271040051593181 219 282132896870653 220 293629121572970 221 305591849893380 222 317955464775255 223 330722431796709 224 343997191876951 225 357756681120894 226 371936643034563 227 386637141504576 228 401910751715995 229 417660516248302 230 433925567755513 231 450829846877518 232 468307779372112 233 486305068008083 234 504969052401246 235 524323909600412 236 544244349607469 237 564824910038325 238 586196691870236 239 608239010175524 240 630929752651011 241 654465041821607 242 678817753421789 243 703846576443028 244 729719987802048 245 756554772079872 246 784167616828586 247 812598005957381 248 842083235518820 249 872519084313232 250 903772690132274 251 936100777785263 252 969574342626056 253 1003950096865846 254 1039363338150132 255 1076072211380272 256 1113870941423555 257 1152673307479002 258 1192829178428713 259 1234323133317756 260 1276870344320895 261 1320736368478771 262 1366164146150302 263 1412829733613442 264 1460744752819765 265 1510341770490729 266 1561472575098780 267 1613850041857112 268 1667897868289925 269 1723790494597226 270 1781085517311287 271 1839952751608521 272 1900875702980222 273 1963527983730784 274 2027683158492398 275 2093935731178395 276 2162322259495234 277 2232307374438981 278 2304281064687826 279 2378719713811705 280 2455084786304438 281 2533296477355218 282 2614107783555919 283 2697337058880441 284 2782415911390843 285 2870006965643596 286 2960492486257890 287 3053112948170468 288 3148038137692528 289 3246132514897382 290 3346915317185531 291 3449884966046492 292 3556005555405724 293 3665450739995553 294 3777271815739114 295 3891996229457092 296 4010510019739802 297 4131967989524867 298 4256074673020639 299 4384085040433144 300 4515829635999925 301 4650257640785598 302 4788349540883710 303 4930875689132579 304 5076598279338957 305 5225598089297046 306 5379355296136414 307 5537218208859802 308 5698186102539400 309 5863752648327607 310 6034389442588059 311 6208499840295644 312 6386723622917017 313 6570632305543642 314 6758972610084608 315 6951012197015391 316 7148757678627061 317 7352163518231498 318 7559393973442534 319 7771815554090803 320 7990881385359564 321 8214669960016189 322 8442989907827891 323 8678275301941987 324 8919731995931746 325 9165508353256535 326 9417815018206459 327 9677702444746659 328 9942605588403304 329 10213174098651700 330 10492077850846034 331 10777565282741797 332 11068099852430337 333 11366763967414503 334 11673860816436241 335 11986336413157169 336 12305967091079455 337 12635347888461118 338 12971632745523938 339 13314024074636862 340 13666374889022742 341 14027867395521299 342 14395273184076596 343 14771712454165119 344 15159275998145548 345 15554016575780322 346 15956354219079175 347 16370649477891054 348 16794611861079483 349 17225324325856478 350 17667338681306111 351 18121711962789981 352 18583579859874642 353 19055051895660067 354 19540550024856450 355 20036052627744643 356 20539594147720711 357 21057055724708229 358 21587873760369688 359 22126691734776707 360 22677692542863641 361 23244727902752741 362 23821966944026919 363 24409138200425139 364 25013107865562665 365 25631118834398120 366 26258012467802632 367 26900248243290001 368 27560314079452700 369 28230764312214459 370 28913778531613077 371 29616587135229412 372 30333781864234094 373 31061341318890575 374 31807931056236970 375 32573776944871527 376 33350366201564346 377 34142981581006984 378 34958312360308790 379 35788082837946281 380 36630530073770231 381 37496100587849264 382 38381852782262539 383 39279154904296863 384 40196801576219933 385 41139779681557735 386 42097108777956489 387 43070465101504165 388 44071240458394887 389 45092553861198468 390 46126994377496795 391 47186892638332491 392 48274190911402437 393 49375872092378611 394 50498120728711824 395 51652009498462176 396 52826258443588681 397 54016325978654597 398 55237593501993718 399 56487566185918193 400 57752448278888989 401 59043686792739429 402 60370374624741268 403 61716886210936648 404 63083342002120427 405 64487089913894154 406 65919946892485109 407 67369195650116980 408 68851773594775096 409 70372833114438348 410 71913161966659706 411 73479239822534942 412 75088661336569314 413 76726693831716927 414 78384059857781443 415 80082698261174886 416 81821732193652246 417 83579970032073863 418 85371559442880646 419 87212020194221228 420 89079884303551423 421 90971966086002037 422 92913857906757203 423 94896693272761122 424 96899801601852847 425 98945607582660170 426 101044753071334764 427 103169810708815448 428 105326301696607723 429 107541197012189593 430 109796146744062408 431 112074297470411621 432 114405972310780987 433 116793873669141494 434 119206582521846503 435 121660492004465527 436 124180778697960955 437 126738981326321330 438 129325888797781251 439 131978133839371694 440 134687496676567640 441 137421833175653903 442 140209672121907724 443 143070471382249601 444 145966310140599896 445 148899538618714537 446 151910179607479231 447 154976639865511711 448 158070533562159743 449 161232458737054358 450 164471763064232920 451 167743354472052522 452 171064586620312545 453 174474634878779915 454 177937158946183456 455 181432914332993179 456 185012827524678693 457 188671714840429842 458 192361445598319831 459 196116699826894320 460 199970422815115643 461 203871816868896376 462 207816499504291524 463 211862104903386555 464 215985062980408447 465 220140145197938539 466 224379932754385952 467 228724969378684340 468 233112487212040633 469 237558253727473819 470 242121086904350940 471 246756475106345237 472 251429485595369610 473 256208902637740083 474 261096467936115926 475 266022490293139728 476 271026845502264581 477 276162301940439556 478 281362961721448602 479 286612331889505749 480 291991088839505303 481 297476315752770491 482 302999060666363540 483 308625029416602042 484 314392436721346850 485 320216440964460269 486 326106868149273247 487 332149270630711806 488 338291729656035092 489 344475945676107256 490 350792152700478305 491 357254944487968750 492 363766452718061588 493 370369209603860042 494 377144123190861829 495 384008541988808630 496 390926136185778403 497 398006795356732021 498 405232851740045052 499 412503017988523738 500 419896143286526081 501 427476995782762512 502 435134172583013738 503 442864731388306061 504 450789559254056077 505 458851773532024806 506 466959640720045974 507 475228001841671773 508 483692896854031816 509 492220769414034559 510 500851939376468448 511 509706029125961227 512 518683139019863428 513 527716451465505916 514 536951679625461127 515 546383707692327010 516 555868509915932716 517 565496215257293403 518 575369934876752889 519 585347620684177844 520 595403494223639700 521 605703807345986956 522 616191638968627628 523 626729056366666609 524 637457540672982317 525 648446547025159677 526 659518755337723742 527 670704158014485525 528 682174111092878922 529 693812933568479578 530 705509161910969642 531 717450853380157974 532 729656334238843268 533 741926743406510811 534 754358754437210158 535 767108991111090275 536 780001807118779134 537 792974427231876871 538 806249643584217785 539 819778903495684632 540 833362414460401090 541 847168244023050489 542 861315360829263999 543 875574608725880255 544 889953209394247702 545 904689745371061987 546 919657229726604804 547 934681351071427062 548 949998119152472969 549 965664784742940603 550 981414180965928835 551 997340683929081774 552 1013673364690303241 553 1030202165271021302 554 1046808168475025957 555 1063782460213174875 556 1081097944420569914 557 1098474399432430573 558 1116103061921056912 559 1134173394552670357 560 1152397205369862582 561 1170740951241792529 562 1189528195242022008 563 1208629445377000874 564 1227784877209032381 565 1247281968570928579 566 1267238068432920467 567 1287303478992425044 568 1307555848394430046 569 1328319610305462087 570 1349352955837963346 571 1370455827295621334 572 1391998999350584735 573 1413995993122313172 574 1436064934707228331 575 1458411828055213797 576 1481323172493679755 577 1504446647352419564 578 1527683082975273622 579 1551460485186214541 580 1575661582916772899 581 1599913697290728765 582 1624555596510304384 583 1649792731897375828 584 1675178894449746319 585 1700753278427506757 586 1726962518990382711 587 1753540889610255840 588 1780175580915635674 589 1807326696635802429 590 1835075159834905579 591 1862914188754886708 592 1891049190874963724 593 1919896317021979915 594 1949037793116568119 595 1978275755849598154 596 2008162817530847223 597 2038616458581048708 598 2069119229645119332 599 2100055247650759486 600 2131753999653018604 601 2163660495926997143 602 2195744571904635479 603 2228605371678856854 604 2261968344425390347 605 2295369166354356784 606 2329363211326030876 607 2364134869660503492 608 2399028258090390933 609 2434223541479253222 610 2470305424283757210 611 2506795266314469969 612 2543353982397334512 613 2580678074299603678 614 2618752242065713753 615 2656878316020010963 616 2695471484864438891 617 2735030079707568575 618 2774881788549468367 619 2814885025560472223 620 2855824221921045617 621 2897440839973488564 622 2939072944096948955 623 2981370848709677920 624 3024669429318723790 625 3068140250727719766 626 3111901689361234891 627 3156751958698136449 628 3202164720328271887 629 3247606639498978020 630 3293934227670074748 631 3341244140329012946 632 3388618622852474152 633 3436478249697567346 634 3485544523799718694 635 3535025644406358487 636 3584613431028861720 637 3635311149732324598 638 3686913719546877023 639 3738508492039409529 640 3790830865523526132 641 3844425731578142765 642 3898271778474405702 643 3952374321886315532 644 4007795227768054953 645 4063985423746779976 646 4120153144757087868 647 4177324771229729150 648 4235768350430516588 649 4294306609142702181 650 4353324873961571588 651 4413831824241370448 652 4474923721296294616 653 4536055738443478795 654 4598481721279278468 655 4662103282144184921 656 4725697978625301988 657 4790062941822540269 658 4856026400366360399 659 4922360160173636011 660 4988887575995293371 661 5056987795406226858 662 5126129529491265743 663 5195187179257774152 664 5265356581035338444 665 5337153705991475226 666 5409103484573729474 667 5481496497993910508 668 5555701729922807584 669 5630724852798355725 670 5705698087426401570 671 5782152189969672651 672 5860167911557861107 673 5938149862923720150 674 6016915403351369859 675 6097663984119250156 676 6178956940737692926 677 6260346351001283408 678 6343582996859314970 679 6428213696759517967 680 6512693131395136725 681 6598370920212302679 682 6686106750267304617 683 6774094886624669393 684 6862448655417171242 685 6952978072958526739 686 7044638202055960752 687 7136135009961612134 688 7229292283386443771 689 7324465061165858269 690 7419620776865394283 691 7515532086797872199 692 7613872117908180759 693 7713003642722809216 694 7812095299476465496 695 7913320531290552679 696 8016389050491451519 697 8119241246388945555 698 8223343613344459188 699 8330016285828479198 700 8437100319595723247 701 8544422096143926871 702 8654318214549108235 703 8765757290261928078 704 8876898922373571163 705 8989859737248700406 706 9105390274038145690 707 9220959761188396433 708 9337202056261654048 709 9456379896168922608 710 9576690988419965915 711 9696783749129151389 712 9819296429045692700 713 9944215787588076856 714 10068867784667448094 715 10194770737062002118 716 10323843776321699303 717 10453568721927230678 718 10583344238897521866 719 10716119543812759684 720 10850971338673046595 721 10985377344578155303 722 11121723062058194192 723 11261304747527946178 724 11401041352099736038 725 11541298702750169753 726 11685056027309395527 727 11830408161104083615 728 11975321132344199853 729 12122924019452695993 730 12273629072560842614 731 12424046819664389789 732 12575646500913309520 733 12731106309564915692 734 12887566861152303909 735 13043823971648616836 736 13203519796470673661 737 13365970700038949297 738 13527824614184826688 739 13691679360150762167 740 13859558289607069873 741 14027794350485453695 742 14196315089458024541 743 14368949678943331672 744 14543789014242592836 745 14717929831882502654 746 14894992861519539237 747 15076003207554725940 748 15256760642080108700 749 15438540327695380158 750 15624959173161895357 751 15812867598420708356 752 16000246853171997845 753 16191498301205755036 754 16386353501498455269 755 16580475201222685570 756 16776574350350631708 757 16977614860672030702 758 17179333449961897777 759 17381002743959344404 760 17587435267854910242 761 17796862487072023190 762 18005302691367973980 763 18216832943910324722 764 18433321412605150942 765 18649676083616967275 766 18866780484812468767 767 19089385443754425138 768 19314145416881157592 769 19537978111548731628 770 19766085610104803330 771 19998840976109031187 772 20230766076590839510 773 20464532104165505076 774 20704288249187222568 775 20945201254410769625 776 21185621444266239371 777 21431468801922630810 778 21681314843916468373 779 21929872787957823796 780 22181591811925205015 781 22439458911324620477 782 22697434428951856523 783 22955751967865859415 784 23220500348785115657 785 23488286970358537124 786 23754681186122179309 787 24025689325656864584 788 24302609324062846476 789 24578675944149397634 790 24856302351349056391 791 25141095792106574935 792 25427728580060236250 793 25713307899088007117 794 26004963741956875063 795 26301871722797704373 796 26597203422402122876 797 26895632637707130269 798 27201587384744575858 799 27508062950545804975 800 27814316694543821070 801 28127978525037595069 802 28445824780632990136 803 28761759918531531067 804 29082544300088033455 805 29410746317107355569 806 29738189513064642890 807 30066733573604579238 808 30403738421323058026 809 30743521311736090723 810 31081571583785998689 811 31426294719538116348 812 31777808356033539062 813 32127506649030637926 814 32480061615363805563 815 32841709231532770322 816 33204516477085106907 817 33566364431035578559 818 33936612671109327490 819 34312502593013877643 820 34685932866452628762 821 35064295753138245483 822 35451841240434989453 823 35838895364030650282 824 36226380473140469213 825 36623715695261065794 826 37025082467599028732 827 37423926362798119001 828 37829937822266938938 829 38244596711346739588 830 38657299045533561718 831 39072393434987698736 832 39498330455982989881 833 39926357793121924587 834 40352503244786775961 835 40788012471215096084 836 41230981290536864778 837 41670948591099867214 838 42115724231527628733 839 42571717154990665699 840 43027726350682952886 841 43483254777723944219 842 43950084859950328157 843 44422578521388726453 844 44891666907187499666 845 45368256540107496126 846 45855698696223873220 847 46341203810179500358 848 46828363968610697384 849 47328281395735144973 850 47831586064908175796 851 48331898656749359640 852 48842453055108633218 853 49362694666682850058 854 49879451156982578943 855 50400621717132612937 856 50935314859455520206 857 51470851876170950912 858 52004728725928956764 859 52551373376303160934 860 53105759435618695942 861 53655799303072685534 862 54213442855452799503 863 54784514970536976233 864 55353908672824937156 865 55923899686907481757 866 56508694898909298936 867 57098622895381202733 868 57684271053833775852 869 58280882653168172519 870 58889864764634667923 871 59495005480489601436 872 60103828581136713002 873 60728738334803638365 874 61355731794664952964 875 61979600965661098056 876 62617654749710955830 877 63266042272855919753 878 63909135643734688824 879 64559623354902768903 880 65226499322347056140 881 65892289516187802418 882 66557253717987851062 883 67239151965058337030 884 67928466029513898760 885 68612061318685898598 886 69307099506519830079 887 70017686907321111532 888 70724292573164842587 889 71433441478065466645 890 72161471864953394876 891 72893342108622955282 892 73620334996150186007 893 74362797904315967872 894 75118768674682488512 895 75868562805919236850 896 76625140642319553693 897 77401448978895049243 898 78177710025716374923 899 78951318859055069433 900 79744005275864056614 901 80547021159396529282 902 81342775039974404561 903 82150108499184733519 904 82976694966400870102 905 83799485146563238759 906 84623202676672886477 907 85468779444328783698 908 86320583064762013513 909 87165480689053378093 910 88026900757107876979 911 88905646928687723686 912 89777496030018229079 913 90655020740366389982 914 91555981648671661915 915 92458508120128858030 916 93356128258385336740 917 94274891459623496152 918 95207622715867100724 919 96131516083017757051 920 97066668392332980260 921 98025317849438018008 922 98980814478855665447 923 99935081734200165128 924 100914297506918685777 925 101902880694419875845 926 102882289838974462995 927 103878919065937366718 928 104897389782356496300 929 105908528355132481955 930 106923637581382793785 931 107966210520807439228 932 109012680360323944810 933 110051554899510786647 934 111113443358140903283 935 112193754979486836925 936 113263720728794556175 937 114344040959539209923 938 115452638622283751424 939 116559339889294375760 940 117662060836785566277 941 118792832441550028115 942 119936993296736813028 943 121069537118601371211 944 122219502050270357809 945 123396559608394234979 946 124566287404114567561 947 125737586108145338052 948 126940628884490601463 949 128150775991648465577 950 129350221442428792520 951 130574213995423889334 952 131821985297445490405 953 133058104030094757516 954 134302953746314406697 955 135581368127573271196 956 136859932625414890268 957 138131135552194008927 958 139433374794404566737 959 140754034825068518665 960 142060558249942153534 961 143384046713736232110 962 144740632978238297501 963 146090511471103096805 964 147438775930970023145 965 148823216473431216978 966 150219012742856819533 967 151600632409223714289 968 153007824384126747358 969 154445121653977511458 970 155869830487594795926 971 157300788607130476577 972 158771045409862193217 973 160244486439286194632 974 161706543172239120588 975 163202342502113326001 976 164722727607263536822 977 166226517652071695937 978 167745983232942834636 979 169305297158683188751 980 170859357335192201326 981 172407757920036756942 982 173996780088441383403 983 175602626983554453817 984 177190541145042068390 985 178804347747457835268 986 180455607309411881216 987 182093921616697983933 988 183735008608763712265 989 185421477712958956137 990 187115367612823060024 991 188793231262249537675 992 190507065946851081182 993 192252897307820555253 994 193979918288602521510 995 195720304217426617285 996 197507991510098899235 997 199292952708916003683 998 201067296551281399996 999 202886541504950739001 1000 204729471329376445398