0 1 1 1 2 2 3 2 4 4 5 5 6 8 7 10 8 15 9 18 10 26 11 32 12 45 13 55 14 74 15 90 16 119 17 145 18 188 19 228 20 291 21 351 22 442 23 532 24 664 25 796 26 982 27 1172 28 1435 29 1708 30 2076 31 2462 32 2972 33 3512 34 4214 35 4966 36 5929 37 6965 38 8272 39 9688 40 11457 41 13383 42 15762 43 18362 44 21543 45 25031 46 29264 47 33922 48 39533 49 45717 50 53112 51 61280 52 70992 53 81737 54 94438 55 108506 56 125048 57 143387 58 164852 59 188672 60 216433 61 247249 62 283014 63 322734 64 368671 65 419702 66 478514 67 543852 68 618912 69 702300 70 797818 71 903932 72 1025149 73 1159779 74 1313166 75 1483492 76 1677092 77 1892012 78 2135740 79 2406210 80 2712279 81 3051796 82 3435236 83 3860412 84 4339685 85 4870868 86 5468548 87 6130654 88 6874400 89 7697909 90 8621460 91 9643518 92 10787976 93 12053826 94 13469214 95 15033898 96 16780989 97 18711269 98 20863692 99 23240482 100 25887460 101 28808709 102 32058066 103 35642054 104 39623927 105 44013354 106 48884636 107 54251456 108 60201017 109 66752016 110 74006786 111 81990388 112 90822883 113 100537189 114 111274056 115 123076150 116 136108447 117 150425631 118 166221024 119 183564054 120 202681113 121 223659559 122 246764450 123 272105080 124 299991683 125 330560061 126 364173102 127 400998678 128 441461159 129 485767096 130 534412594 131 587650714 132 646061100 133 709952498 134 780001942 135 856584972 136 940492092 137 1032178463 138 1132566584 139 1242206520 140 1362174435 141 1493133294 142 1636338034 143 1792585660 144 1963338826 145 2149553249 146 2352933026 147 2574621882 148 2816604404 149 3080246232 150 3367857432 151 3681065440 152 4022558091 153 4394271242 154 4799330928 155 5240035800 156 5720019697 157 6242007272 158 6810220848 159 7427885194 160 8099904239 161 8830088558 162 9624130848 163 10486527402 164 11423883619 165 12441497587 166 13547030220 167 14746716006 168 16049435601 169 17462515691 170 18996246166 171 20659227046 172 22463375515 173 24418773824 174 26539216896 175 28836511164 176 31326617724 177 34023346828 178 36945157160 179 40108185518 180 43533768394 181 47240741133 182 51253755074 183 55594773878 184 60292265172 185 65371815012 186 70866281866 187 76805443462 188 83227208407 189 90166201102 190 97666135616 191 105767235788 192 114519885546 193 123970772550 194 134177940758 195 145195535224 196 157090392735 197 169925254334 198 183777044332 199 198718405938 200 214837831750 201 232219364073 202 250964755422 203 271171161172 204 292955524678 205 316430075508 206 341729152848 207 368982305270 208 398343783371 209 429963019147 210 464017042288 211 500678099014 212 540149268051 213 582628956831 214 628350018532 215 677540841136 216 730468293765 217 787395100812 218 848626976898 219 914465950836 220 985262077792 221 1061362349421 222 1143167409730 223 1231075658538 224 1325545433595 225 1427033879959 226 1536065102524 227 1653163338436 228 1778927628498 229 1913958792769 230 2058941219806 231 2214563102690 232 2381605993996 233 2560857714940 234 2753210385060 235 2959565371148 236 3180940560339 237 3418366661909 238 3673004560266 239 3946032227392 240 4238773064902 241 4552572627234 242 4888938943634 243 5249408186138 244 5635698043360 245 6049561398554 246 6492953925408 247 6967874770188 248 7476549637863 249 8021257390417 250 8604530001722 251 9228963899494 252 9897438285743 253 10612909961485 254 11378651641452 255 12198028900534 256 13074760244747 257 14012674714059 258 15015995629618 259 16089077279268 260 17236714421278 261 18463856355979 262 19775944444458 263 21178601742586 264 22678000985362 265 24280527826810 266 25993181953296 267 27823211823736 268 29778551793291 269 31867426093177 270 34098825099770 271 36482076132246 272 39027362262851 273 41745257329799 274 44647290972456 275 47745445069852 276 51052768995938 277 54582834498977 278 58350405514572 279 62370848284200 280 66660860419143 281 71237832831072 282 76120643147226 283 81328965792408 284 86884135278867 285 92808400519329 286 99125863980356 287 105861676037782 288 113043056486099 289 120698424468767 290 128858509388076 291 137555411635458 292 146823810524251 293 156699950727159 294 167222955508780 295 178433733448878 296 190376405937866 297 203097128402607 298 216645641779964 299 231074002089658 300 246438266415851 301 262797124286940 302 280213729585230 303 298754226773366 304 318489741091503 305 339494792238008 306 361849456267506 307 385637658890144 308 410949523597202 309 437879536259434 310 466529095223456 311 497004538396358 312 529419912375470 313 563894852701140 314 600557590520866 315 639542676145832 316 680994243278046 317 725063565450521 318 771912599547666 319 821711364145422 320 874641785863358 321 930894888013624 322 990674965295478 323 1054196570551380 324 1121689045455119 325 1193393292558070 326 1269566691952914 327 1350479645137134 328 1436420910122416 329 1527693902988547 330 1624622486664376 331 1727547015397490 332 1836830615375537 333 1952854956651267 334 2076027066979248 335 2206774815066852 336 2345554302483468 337 2492845041456443 338 2649157973498758 339 2815030324291964 340 2991034301739615 341 3177771609835554 342 3375882883329450 343 3586041841876852 344 3808965523305974 345 4045408058733831 346 4296171771652754 347 4562100554149496 348 4844091904712079 349 5143089885212220 350 5460098176513630 351 5796172595423798 352 6152435253832650 353 6530066614489144 354 6930320846706984 355 7354517399592332 356 7804057655216094 357 8280415997753506 358 8785157873580580 359 9319930334788518 360 9886481624965619 361 10486651175737555 362 11122390847114884 363 11795754356032884 364 12508920311059135 365 13264181052479725 366 14063967633131026 367 14910838050438128 368 15807504338049042 369 16756820171317746 370 17761810248473522 371 18825657252503932 372 19951733715877639 373 21143588323662494 374 22404980472446624 375 23739865901777978 376 25152434175903339 377 26647093633407440 378 28228512040067414 379 29901600849970340 380 31671559299058378 381 33543857974966808 382 35524286643992474 383 37618937131636862 384 39834255200926456 385 42177022751250460 386 44654414093373158 387 47273977480601250 388 50043696155516639 389 52971969235047008 390 56067677936406356 391 59340165846403446 392 62799310769237697 393 66455504420351509 394 70319730376999598 395 74403543248458048 396 78719153251938616 397 83279404924171236 398 88097868890560402 399 93188820198092688 400 98567337894792646 401 104249283080960801 402 110251406969683222 403 116591328772814462 404 123287652971541145 405 130359947175356268 406 137828869395084358 407 145716146037847050 408 154044710043986316 409 162838679208998359 410 172123506120920338 411 181925957031561908 412 192274274612494758 413 203198157633244682 414 214728937643060382 415 226899559753469186 416 239744774449684825 417 253301119819305246 418 267607129802479642 419 282703318258318532 420 298632405077551500 421 315439302533977795 422 333171360808103728 423 351878357133062654 424 371612762413289135 425 392429733743744492 426 414387403955573260 427 437546878164940154 428 461972548238324721 429 487732094113339091 430 514896825351294032 431 543541688068269378 432 573745635933119241 433 605591643653788069 434 639167109986341312 435 674563878839849600 436 711878677087548191 437 751213144485104524 438 792674309320904488 439 836374628488498466 440 882432504280364164 441 930972336116875960 442 982125082078976156 443 1036028323975139602 444 1092826877525341953 445 1152672872645914788 446 1215726416542244154 447 1282155691310658496 448 1352137674572569793 449 1425858256735137927 450 1503513024208581144 451 1585307398935611246 452 1671457489678481769 453 1762190256723142545 454 1857744437206879992 455 1958370738230064098 456 2064332842722517229 457 2175907634556598542 458 2293386292024399702 459 2417074548943546212 460 2547293883441673582 461 2684381819484866554 462 2828693219346071998 463 2980600630469481540 464 3140495690739419629 465 3308789526125940622 466 3485914278676093346 467 3672323560971896358 468 3868494117642585970 469 4074926343311054067 470 4292146089379854094 471 4520705252851160146 472 4761183741177259963 473 5014190140118929201 474 5280363850581473704 475 5560375844533802740 476 5854930988980572917 477 6164768899905800485 478 6490666469869657762 479 6833438830974960476 480 7193942104033324298 481 7573074482688958129 482 7971779223683336136 483 8391045865517191046 484 8831913481066244750 485 9295472045530323134 486 9782865974528663488 487 10295295657585957316 488 10834021306876021172 489 11400364674139775178 490 11995713237465750538 491 12621522121338939302 492 13279318651261556442 493 13970704498608927036 494 14697360635520845028 495 15461049728406245520 496 16263621528392173345 497 17107015539691327451 498 17993266884003869030 499 18924509272559938422 500 19902981386249173760 501 20931030182993543635 502 22011117839055013204 503 23145825426506157054 504 24337860465163824998 505 25590061008330357539 506 26905403859147863560 507 28287009106506942210 508 29738149064341707254 509 31262253303675936799 510 32862918378518214432 511 34543913404468859466 512 36309190640460833248 513 38162891669217610102 514 40109358910158512182 515 42153142462316610872 516 44299012630329209298 517 46551967496236350952 518 48917246547653301708 519 51400339051216993682 520 54006998879835974255 521 56743253767483602396 522 59615421440898173628 523 62630119842989968608 524 65794284683575456440 525 69115180726925384031 526 72600420886126365014 527 76257978679312413996 528 80096209003123659463 529 84123861872000782327 530 88350105018027537704 531 92784539038397382812 532 97437221981763164398 533 102318686040688584238 534 107439964298575046482 535 112812609116673109662 536 118448721230804184948 537 124360969996419805770 538 130562625040788484916 539 137067578544756667066 540 143890379673940177567 541 151046259092369556569 542 158551166415630626970 543 166421797169585443516 544 174675633529476545397 545 183330973956534411041 546 192406977509939924718 547 201923696415500017780 548 211902124262201718999 549 222364231780409168847 550 233333019261707861804 551 244832555849415979306 552 256888036549689431847 553 269525825364727070094 554 282773517294879350498 555 296659985674951838680 556 311215449601541800649 557 326471525865520592543 558 342461302276245860702 559 359219394618858769942 560 376782026387626894427 561 395187091235370964125 562 414474239672254477026 563 434684947516727832014 564 455862610163885760291 565 478052617593074369956 566 501302456861798788270 567 525661794274892221944 568 551182586816211100186 569 577919172138358978065 570 605928389705427600408 571 635269679321071387054 572 666005212821731674067 573 698200001924765956803 574 731922041383361577448 575 767242427005874916798 576 804235511261466551341 577 842979032397267869400 578 883554283568153876368 579 926046254060332357198 580 970543813110155362342 581 1017139864331773042163 582 1065931545489065917992 583 1117020397321716877538 584 1170512580641853571934 585 1226519060857907694130 586 1285155843884082115046 587 1346544177775388475556 588 1410810809064343643657 589 1478088203044358917377 590 1548514822284928449396 591 1622235367234897784536 592 1699401078815701368796 593 1780170001161852993818 594 1864707310352469715308 595 1953185601264557208128 596 2045785244677132578826 597 2142694700384551807309 598 2244110905096117524314 599 2350239614142937033908 600 2461295822800164075884 601 2577504139122892460979 602 2699099241539415167206 603 2826326285570751623090 604 2959441400782898325692 605 3098712134382176208908 606 3244417990873903533974 607 3396850915783360527894 608 3556315881649247720299 609 3723131415399342613756 610 3897630234611269369270 611 4080159822374657832674 612 4271083118081036769165 613 4470779143932426571862 614 4679643754878616677916 615 4898090321287706390942 616 5126550543034839264174 617 5365475193235509995256 618 5615335001907396821036 619 5876621466084707663196 620 6149847808926634775765 621 6435549861983239268192 622 6734287106113030992274 623 7046643632160732693184 624 7373229270575562274566 625 7714680637291739242928 626 8071662359511446416208 627 8444868214153442465926 628 8835022457883892837477 629 9242881066120514328345 630 9669233176064271608724 631 10114902434919959171896 632 10580748565406211714826 633 11067668832582479684577 634 11576599742098291870956 635 12108518635805707335790 636 12664445533856034614814 637 13245444870130894499198 638 13852627490210743803998 639 14487152538581884952036 640 15150229625491667369932 641 15843120878888790214944 642 16567143294250919142166 643 17323670965297541526778 644 18114137632033332002270 645 18940039105443199009261 646 19802936030245977406236 647 20704456520047256046508 648 21646299152650328132898 649 22630235833511561159729 650 23658115042917025379764 651 24731864947065799456416 652 25853496917999983188988 653 27025108913242336067715 654 28248889291073821972250 655 29527120481382948192830 656 30862183120728635397965 657 32256560038929894317303 658 33712840740343524783014 659 35233725732745505101776 660 36822031383404502885591 661 38480694618992581264785 662 40212778187359349305364 663 42021475759572256813690 664 43910117630806000550409 665 45882176258165770813742 666 47941272436816920267710 667 50091181310003095101506 668 52335839059467910443197 669 54679349427060154404123 670 57125990961659295024442 671 59680224094979385634306 672 62346698990621960543007 673 65130263220167727440202 674 68035970263663493579404 675 71069087835846478643098 676 74235107091347571282196 677 77539751654949009318014 678 80988987589077386954884 679 84589033186375069075258 680 88346369761687541438760 681 92267752269957587819806 682 96360220989909317770238 683 100631113035379165330608 684 105088075003291790846428 685 109739075452052758068829 686 114592418592230200792668 687 119656757811582238731570 688 124941110493135891730963 689 130454872672842009418046 690 136207835076515037448858 691 142210199003036151331870 692 148472593678922411729860 693 155006093467474381528030 694 161822236647622198859380 695 168933044057479753665928 696 176351039412612643441535 697 184089269501162739564326 698 192161326165846603901626 699 200581368177201196030222 700 209364145013502480634487 701 218525020548808119426386 702 228079998775639995172430 703 238045749455419996880824 704 248439635940246439123524 705 259279742945095784714254 706 270584906637405414989386 707 282374744703113343434290 708 294669688886107293417076 709 307491017533867101056588 710 320860890783226540848404 711 334802385786145496066560 712 349339534753735982532564 713 364497363078605402504513 714 380301930465807342459186 715 396780372185351599430366 716 413960943536745501020264 717 431873064483755796978644 718 450547367718606376554718 719 470015746951003656850164 720 490311408858957983261626 721 511468925325557552493508 722 533524289585897734823392 723 556514972728226779443342 724 580479984370722615644792 725 605459933768563451415755 726 631497095380417369979766 727 658635474949848751269048 728 686920880349524007474803 729 716400993034296988454744 730 747125444581436986794534 731 779145893943900411693336 732 812516110137518596834910 733 847292055756528218781325 734 883531976293792464588504 735 921296490416810673968138 736 960648686444876173155518 737 1001654219922711793462217 738 1044381417819194383124260 739 1088901383977677025664538 740 1135288111644752074343814 741 1183618597421448425234653 742 1233972962777696316714532 743 1286434577177171080453832 744 1341090189283915702671965 745 1398030059985901136308481 746 1457348104054927080429076 747 1519142033850262440574500 748 1583513512251771279978787 749 1650568307885585358086522 750 1720416460213702585853040 751 1793172447188848832664060 752 1868955363451905142104447 753 1947889101393283949912665 754 2030102543482818199109220 755 2115729757790479115768122 756 2204910205552191044581783 757 2297788952283952592343068 758 2394516891771839593854398 759 2495250974000986600154632 760 2600154446849251388309664 761 2709397102146528816740662 762 2823155536449650902264754 763 2941613416648632966922704 764 3064961761305885456106598 765 3193399227334762080157842 766 3327132413499612740604566 767 3466376169808982884140190 768 3611353924895030781486648 769 3762298019889525827127077 770 3919450061532320551704672 771 4083061282433566789824930 772 4253392921901951905350439 773 4430716614641997088635067 774 4615314801444366575022152 775 4807481148523484294186150 776 5007520990375185343281213 777 5215751782127992932049043 778 5432503577048540901056176 779 5658119514460558339149824 780 5892956334566749186142552 781 6137384904683765747937826 782 6391790774251550098750974 783 6656574742341335946612146 784 6932153455940870171164597 785 7218960021916833367837483 786 7517444651897976843265364 787 7828075322114441135867050 788 8151338468451852385262057 789 8487739697849073325305806 790 8837804537365977334019862 791 9202079201099504807006416 792 9581131397397539439740712 793 9975551155552176342756706 794 10385951695603327522921306 795 10812970319389350028624998 796 11257269347718275881165062 797 11719537080701021470871147 798 12200488807427154024374736 799 12700867840876546433680446 800 13221446605622160901467569 801 13763027753014090149873440 802 14326445332845891862408002 803 14912565994932465461249880 804 15522290251121079523186265 805 16156553769843613680633154 806 16816328735330804554828026 807 17502625242212328563908414 808 18216492759305328006952123 809 18959021631865080611137230 810 19731344657869104143140142 811 20534638706089385734449508 812 21370126413384030118090473 813 22239077927372027207672534 814 23142812733878429830754874 815 24082701533647444079275228 816 25060168209767629479581770 817 26076691848561940636321871 818 27133808857549790944473700 819 28233115141407023458580938 820 29376268381805461695795762 821 30564990380145356522806703 822 31801069511454112726035324 823 33086363246462524440797216 824 34422800792646834774751964 825 35812385809152294134449393 826 37257199249030995200882902 827 38759402281516527593730554 828 40321239350548857043874627 829 41945041319976989783657467 830 43633228764576591684498220 831 45388315354908845136858478 832 47212911398231947290085889 833 49109727480979338990518662 834 51081578278248479394337152 835 53131386473186343325146008 836 55262186855114148769505224 837 57477130536528870342456585 838 59779489361397540022404058 839 62172660442007376614710466 840 64660170900544999176960519 841 67245682749661974265375524 842 69932997992150385666066236 843 72726063870843017545175428 844 75628978353015357216243169 845 78645995777118680014711173 846 81781532750488438953858066 847 85040174222423202789912102 848 88426679825869832306963020 849 91945990408521183608355674 850 95603234851389462900877606 851 99403737091911154007322902 852 103353023454722156678048271 853 107456830203240562344701079 854 111721111420532034903189330 855 116152047128501643323230038 856 120756051759497654828168062 857 125539782885095262050883568 858 130510150322044594429621630 859 135674325515685355243741288 860 141039751327014394610604435 861 146614152119045441564925272 862 152405544275167970396022858 863 158422247040275823235802726 864 164672893824228328246756642 865 171166443853332179824507981 866 177912194316614929099141714 867 184919792887273688727708156 868 192199250773648495508941089 869 199760956174568126836495530 870 207615688301385980820660318 871 215774631835777731616175916 872 224249391993996185003624497 873 233052010060629256888170356 874 242194979571365087818873956 875 251691263001524992988186170 876 261554309149129846849848286 877 271798071062705907677178611 878 282437024712333650110578048 879 293486188247311098685884520 880 304961142049174188823628407 881 316878049416320656380498225 882 329253678099745823310793296 883 342105422518710329975312496 884 355451326887168153554378229 885 369310109072035755079613698 886 383701185426033473284935156 887 398644696408116421791271184 888 414161533246741773125039237 889 430273365450589778680712770 890 447002669435145923962617562 891 464372758061013073021083856 892 482407811366199701299224387 893 501132908279143399430612759 894 520574059609267823367818904 895 540758242092348516610302642 896 561713433802788277851681686 897 583468650700206431223117857 898 606053984638534591049039416 899 629500642594751358212387074 900 653840987462370936349567331 901 679108580156131486001157734 902 705338223390794305255410238 903 732566006869384189405633412 904 760829354262497375650998274 905 790167071702448674210145403 906 820619398193566649790485162 907 852228057650391698075631900 908 885036312985785943399079440 909 919089021948220052521621255 910 954432695152016700024112794 911 991115555986837797261160534 912 1029187602873092743515217985 913 1068700673536073119560972475 914 1109708511789574263327317678 915 1152266836487808056913498912 916 1196433413161698287836177072 917 1242268127983826541617355396 918 1289833064604764048877144676 919 1339192583489969742646679772 920 1390413404328016032919565560 921 1443564691123667339998577128 922 1498718140576053570488092698 923 1555948073339224564674415828 924 1615331528796339422274670789 925 1676948362927937572848105720 926 1740881349938168817449590188 927 1807216287201973521845689274 928 1876042104231409976382737274 929 1947450975206031543506221372 930 2021538435801616297027225980 931 2098403503843414066561637816 932 2178148804556199422378050752 933 2260880699917892516703338413 934 2346709422929001607356022486 935 2435749216284564947379344620 936 2528118476302895289036867997 937 2623939901577023539293942252 938 2723340647247388692745375778 939 2826452484340177182540181416 940 2933411965116413395316009199 941 3044360593853983936484492711 942 3159445004056685335369840346 943 3278817141489515676941225464 944 3402634454085850340211340751 945 3531060088102004919931429178 946 3664263091619074785170195604 947 3802418624743068598893421800 948 3945708177660316945621878766 949 4094319795873907118696111674 950 4248448313838210777906655154 951 4408295596291197545631544836 952 4574070788564840385702154575 953 4745990575146446079785774162 954 4924279447837777757096161588 955 5109169982757132496937987384 956 5300903127601301653262176351 957 5499728498384088770833073056 958 5705904687142060331453598586 959 5919699579794892526740746206 960 6141390685728621348424595741 961 6371265478259020172731671396 962 6609621747625137041110864118 963 6856767965639247687147276196 964 7113023663729294114290129055 965 7378719823468268081385531569 966 7654199281417191504866929376 967 7939817147343530971410754198 968 8235941237737069844786826045 969 8542952523651633456867618562 970 8861245594895109758438796940 971 9191229139561908737765203000 972 9533326441036041674236105317 973 9887975891423913393488205884 974 10255631523656354505567594122 975 10636763561183155016381273248 976 11031858987616882744593736557 977 11441422135212655032685220228 978 11865975294664134273822785488 979 12306059345065086815165524918 980 12762234406646831329759301084 981 13235080515102881392229664179 982 13725198320248088990461631214 983 14233209807784888617676062876 984 14759759047068230784051304709 985 15305512963602470879648828989 986 15871162139313783133360704340 987 16457421639291451469420536346 988 17065031868201706167991053001 989 17694759455027018939458443450 990 18347398169503185578519727458 991 19023769868866207694421853152 992 19724725478458991598693109173 993 20451146004768584421691515020 994 21203943584631176795503922052 995 21984062569133991249434236692 996 22792480646148540555257445198 997 23630209999982555544759452361 998 24498298512292915677763303762 999 25397831002704945199291969364 1000 26329930513499432710988720771