0 1 1 0 2 1 3 1 4 2 5 2 6 6 7 6 8 10 9 13 10 20 11 26 12 39 13 50 14 71 15 87 16 121 17 156 18 208 19 265 20 348 21 440 22 566 23 712 24 906 25 1131 26 1424 27 1766 28 2224 29 2738 30 3390 31 4168 32 5130 33 6266 34 7664 35 9312 36 11332 37 13723 38 16603 39 20004 40 24112 41 28942 42 34708 43 41522 44 49612 45 59031 46 70308 47 83479 48 98992 49 117172 50 138509 51 163404 52 192628 53 226617 54 266290 55 312446 56 366170 57 428413 58 500836 59 584580 60 681547 61 793687 62 923226 63 1072531 64 1244879 65 1443068 66 1671456 67 1933631 68 2234787 69 2580145 70 2976320 71 3429734 72 3948689 73 4541991 74 5219837 75 5993283 76 6875837 77 7881184 78 9026549 79 10329764 80 11811595 81 13495253 82 15407677 83 17577093 84 20037311 85 22825207 86 25982475 87 29555046 88 33596262 89 38163130 90 43322175 91 49145049 92 55715397 93 63122925 94 71470911 95 80871435 96 91453062 97 103356657 98 116740587 99 131779277 100 148670710 101 167630984 102 188904084 103 212758503 104 239495334 105 269445783 106 302982692 107 340514014 108 382498461 109 429439771 110 481900486 111 540500369 112 605931220 113 678953472 114 760414402 115 851246065 116 952486525 117 1065277086 118 1190885611 119 1330706000 120 1486291057 121 1659334407 122 1851728240 123 2065546938 124 2303085685 125 2566868281 126 2859688876 127 3184612052 128 3545030959 129 3944667508 130 4387629782 131 4878431609 132 5422055916 133 6023956894 134 6690160078 135 7427272356 136 8242565982 137 9144015633 138 10140404201 139 11241342655 140 12457421446 141 13800228436 142 15282492464 143 16918170610 144 18722585573 145 20712486413 146 22906286383 147 25324119047 148 27988056227 149 30922249584 150 34153172398 151 37709741271 152 41623669213 153 45929567905 154 50665365117 155 55872468124 156 61596189360 157 67885969959 158 74795927710 159 82385086810 160 90717951069 161 99864903057 162 109902827255 163 120915521475 164 132994534631 165 146239593102 166 160759537607 167 176672977055 168 194109253162 169 213209187777 170 234126388150 171 257027995202 172 282096147669 173 309529078082 174 339542675307 175 372371712871 176 408271884957 177 447521122200 178 490421861201 179 537302903104 180 588521808035 181 644466999334 182 705560952333 183 772262371885 184 845069737195 185 924524356424 186 1011214176992 187 1105777216434 188 1208906445548 189 1321353519946 190 1443934328301 191 1577533693383 192 1723111718902 193 1881709081251 194 2054454728790 195 2242571947609 196 2447386921446 197 2670336614568 198 2912978193224 199 3176997913594 200 3464222877154 201 3776630940868 202 4116363984192 203 4485740293984 204 4887269434255 205 5323666356162 206 5797869491226 207 6313056660117 208 6872665510680 209 7480413244109 210 8140319572613 211 8856728916769 212 9634338442375 213 10478223257962 214 11393867911931 215 12387197119668 216 13464611338942 217 14633022088626 218 15899894249509 219 17273285959753 220 18761897087796 221 20375117117632 222 22123079950172 223 24016718509984 224 26067829892998 225 28289137731807 226 30694365944414 227 33298313165949 228 36116936546046 229 39167436880206 230 42468357329199 231 46039679796254 232 49902938977465 233 54081335060069 234 58599862833059 235 63485442381491 236 68767068939406 237 74475962422373 238 80645738604613 239 87312583926833 240 94515450743412 241 102296257740531 242 110700116897313 243 119775561797936 244 129574807996023 245 140154018902568 246 151573600998489 247 163898509948272 248 177198592589208 249 191548935401633 250 207030256305247 251 223729308208459 252 241739325571119 253 261160487232630 254 282100430900708 255 304674781457552 256 329007739948909 257 355232693584502 258 383492885268402 259 413942113542680 260 446745503030350 261 482080301473505 262 520136761847810 263 561119058647661 264 605246292560028 265 652753540306357 266 703893004978862 267 758935214576183 268 818170336575452 269 881909552139197 270 950486552536653 271 1024259110640790 272 1103610794947423 273 1188952758718044 274 1280725696470906 275 1379401892610883 276 1485487448218126 277 1599524618866941 278 1722094360258921 279 1853818991066844 280 1995365092204266 281 2147446551547306 282 2310827861054897 283 2486327588958030 284 2674822140758738 285 2877249709627453 286 3094614558637248 287 3327991528914658 288 3578530905953566 289 3847463552671724 290 4136106453202497 291 4445868549335520 292 4778257045956107 293 5134884057454899 294 5517473770033357 295 5927870002770322 296 6368044352446999 297 6840104784044394 298 7346304883775842 299 7889053630642149 300 8470925897527905 301 9094673549082581 302 9763237374537689 303 10479759684993564 304 11247597854156587 305 12070338623771809 306 12951813459506544 307 13896114792100700 308 14907613432225771 309 15990976986408464 310 17151189607466805 311 18393572880704425 312 19723808202044343 313 21147960455588399 314 22672503370564170 315 24304346350709671 316 26050863193570980 317 27919922480916378 318 29919920095448431 319 32059813642381722 320 34349159246175930 321 36798150509665264 322 39417660164496712 323 42219284152519462 324 45215388729987534 325 48419160340509232 326 51844658883541330 327 55506874103120949 328 59421785809293873 329 63606427626317194 330 68078955035161694 331 72858717435689689 332 77966334997932386 333 83423780067683365 334 89254463985668538 335 95483329006268556 336 102136946304326068 337 109243619782627444 338 116833496668375759 339 124938684676121658 340 133593376813334799 341 142833983547112540 342 152699273593984427 343 163230523027685664 344 174471673991361345 345 186469502839246527 346 199273799097767078 347 212937554963122916 348 227517166973647562 349 243072649612531907 350 259667862470633940 351 277370750890112721 352 296253601868418269 353 316393315019420519 354 337871690732024978 355 360775735311813487 356 385197985256261211 357 411236850747482334 358 438996980636739780 359 468589648879067138 360 500133165151504952 361 533753309645838960 362 569583794806362941 363 607766754323210514 364 648453262368419564 365 691803883268269503 366 737989255197318607 367 787190708100378132 368 839600919464205406 369 895424608714500088 370 954879274058012558 371 1018195972379761238 372 1085620146862257694 373 1157412502970468542 374 1233849937582849383 375 1315226522556000140 376 1401854547804568047 377 1494065625136099229 378 1592211858923976609 379 1696667084853496598 380 1807828183175938365 381 1926116468483949237 382 2051979162822779204 383 2185890954196350828 384 2328355648524938805 385 2479907917292650072 386 2641115149240563134 387 2812579409541553100 388 2994939515271762246 389 3188873230741750541 390 3395099593195452179 391 3614381372569073164 392 3847527676449583291 393 4095396705434977433 394 4358898670653621390 395 4638998878926463637 396 4936720999526838531 397 5253150518347128972 398 5589438394205278081 399 5946804925166425939 400 6326543840469905001 401 6730026626462659054 402 7158707104978452311 403 7614126272967579779 404 8097917423132134292 405 8611811557083616369 406 9157643111798834785 407 9737356011856188431 408 10353010071998107783 409 11006787763163691638 410 11701001368266625055 411 12438100544435540335 412 13220680319667475560 413 14051489542017175311 414 14933439813887814267 415 15869614930857639894 416 16863280860155272033 417 17917896282786690450 418 19037123736628759010 419 20224841386736554511 420 21485155466383857866 421 22822413416826215190 422 24241217772789538357 423 25746440827821336040 424 27343240129727846132 425 29037074843460241493 426 30833723039421680452 427 32739299947480945985 428 34760277239696145816 429 36903503389853832974 430 39176225177218671736 431 41586110387396961299 432 44141271788101571616 433 46850292436739652890 434 49722252404236576597 435 52766756982648874112 436 55993966467640413336 437 59414627589223926473 438 63040106695783241083 439 66882424770967347166 440 70954294397186505848 441 75269158759729975560 442 79841232813600632917 443 84685546716570849017 444 89817991668264109896 445 95255368267236888977 446 101015437538376252385 447 107116974761289029108 448 113579826264305974426 449 120424969327197684399 450 127674575380404187938 451 135352076656634140744 452 143482236499549160263 453 152091223509729375764 454 161206689749430145033 455 170857853204351137681 456 181075584754250888878 457 191892499867975649568 458 203343055297830276535 459 215463651021522203673 460 228292737729958804967 461 241870930133231039947 462 256241126422674650049 463 271448634186745934599 464 287541303149752229008 465 304569665073398211587 466 322587081222635971719 467 341649897769510260146 468 361817609588643093496 469 383153032852189411557 470 405722486920389907161 471 429595985992523161398 472 454847441057823257848 473 481554872657732592278 474 509800635066551855835 475 539671652450147299036 476 571259667668314185825 477 604661504352927203566 478 639979342988391554196 479 677321011690668604934 480 716800292499250995712 481 758537243944855947928 482 802658540785227128264 483 849297831769859511422 484 898596116407899685124 485 950702141685911092691 486 1005772819826303230283 487 1063973668124277182639 488 1125479272060579045326 489 1190473772854517705254 490 1259151380766035062353 491 1331716915430815694513 492 1408386374688026209236 493 1489387533308729096331 494 1574960573227844277667 495 1665358746856350034192 496 1760849075227862622373 497 1861713082713785856558 498 1968247570263928891134 499 2080765429073610640296 500 2199596496826090666504 501 2325088458635790048629 502 2457607795041160320152 503 2597540779391293161079 504 2745294527236936035173 505 2901298100296523460613 506 3066003667868188276918 507 3239887728550583648423 508 3423452395417294812186 509 3617226747797505377520 510 3821768253152844509635 511 4037664262512533330304 512 4265533583300861627099 513 4506028133406906361278 514 4759834680696437153125 515 5027676672206718298395 516 5310316157679483550142 517 5608555812083820004798 518 5923241062249476816559 519 6255262322772551400635 520 6605557346802774703197 521 6975113697399292036821 522 7364971345660360784702 523 7776225401871278669087 524 8210028986491964824834 525 8667596247899980027621 526 9150205534368986257881 527 9659202727896125377323 528 10196004748144904981407 529 10762103234859809765782 530 11359068417842021890254 531 11988553183731032246037 532 12652297349552778206661 533 13352132153214202882339 534 14089984971938570883476 535 14867884279815249559786 536 15687964856550017773856 537 16552473259757142027463 538 17463773574049089449884 539 18424353450501684913961 540 19436830451110756468449 541 20503958713145880607393 542 21628635949461992131179 543 22813910801220608094536 544 24062990560625679709460 545 25379249281771336756358 546 26766236299002124631223 547 28227685172641420467494 548 29767523083406554419887 549 31389880697396214937179 550 33099102525026050993077 551 34899757797979056211487 552 36796651889895479564746 553 38794838307216223272673 554 40899631278436501426948 555 43116618970856403055000 556 45451677365808434127854 557 47910984824329225783849 558 50501037377358098985682 559 53228664775529014995813 560 56101047335977730811793 561 59125733624754398084827 562 62310659015867624445915 563 65664165169348258425767 564 69195020473432459582620 565 72912441497360294161659 566 76826115504288989543645 567 80946224075448683608334 568 85283467899795037628653 569 89849092785301141638249 570 94654916951490847804674 571 99713359664778865374952 572 105037471282008113119289 573 110640964769841366383821 574 116538248771666764909903 575 122744462296273361730227 576 129275511106970254746649 577 136148105892556966512620 578 143379802306444821272993 579 150989042963311135956830 580 158995201487842769997738 581 167418628713638665599875 582 176280701136018714846237 583 185603871726228309670015 584 195411723220780180113426 585 205729024003900399341049 586 216581786707680652518169 587 227997329659289490705496 588 240004341311894405135606 589 252632947801032227033408 590 265914783776197229416941 591 279883066663096298778263 592 294572674520589319685727 593 310020227662727623654417 594 326264174225665293246040 595 343344879866103839240495 596 361304721788233095232038 597 380188187303781019377245 598 400041977140831016747922 599 420915113725593072480847 600 442859054673394321884086 601 465927811734394418793685 602 490178075452771013349679 603 515669345808357885439568 604 542464069123941633530598 605 570627781532831116701677 606 600229259316838780782961 607 631340676437159175984358 608 664037769597684666011845 609 698400011193918658626033 610 734510790519018231273760 611 772457603613609509451931 612 812332252166039122263858 613 854231051886195347084105 614 898255050797928508834829 615 944510257913212718186984 616 993107882774872641000432 617 1044164586374735082651046 618 1097802743979867069952119 619 1154150720421342900652820 620 1213343158428257057904216 621 1275521280613627468674772 622 1340833205749396109746199 623 1409434279994177085984508 624 1481487423770641444638391 625 1557163495018297779872694 626 1636641669583766635630726 627 1720109839542234052920161 628 1807765030283229554169111 629 1899813837228663063363439 630 1996472883093947039220251 631 2097969296640989479733700 632 2204541213918775789759157 633 2316438303028733882927470 634 2433922313503030979005241 635 2557267651429613842046207 636 2686761981513100590817862 637 2822706857310584211058762 638 2965418380941809200399054 639 3115227893627655093913346 640 3272482698476566331856103 641 3437546816998453201174142 642 3610801780896838590271737 643 3792647460755523561768413 644 3983502933313855062654186 645 4183807389096077616267282 646 4394021082244916829291977 647 4614626324487857147564082 648 4846128525256477836531828 649 5089057280064836294594319 650 5343967509353184636717906 651 5611440650096523237135547 652 5892085902586717266178817 653 6186541534899153124624247 654 6495476247673232689258063 655 6819590601947880410319632 656 7159618512922353701214035 657 7516328812634312063127605 658 7890526884687803105930777 659 8283056374297000347431457 660 8694800977064072425518297 661 9126686310055243180390350 662 9579681868905389871693446 663 10054803074839928377552276 664 10553113415683933218765246 665 11075726685101789600991478 666 11623809324506969886583880 667 12198582872271070196055333 668 12801326525075303961819048 669 13433379816453506190347119 670 14096145417809023371554717 671 14791092067412903259717536 672 15519757633143583814468808 673 16283752314974374699156775 674 17084761993490311271345533 675 17924551730983284715094860 676 18804969431974466426679048 677 19727949670304949357414499 678 20695517690260706864358727 679 21709793589516929643316155 680 22772996692040988804304048 681 23887450119439593712001758 682 25055585569621596670777174 683 26279948312026034357866494 684 27563202409082979422761682 685 28908136173987854772202242 686 30317667875324866901372539 687 31794851699523525309646510 688 33342883982628224285398268 689 34965109723349640600734344 690 36665029389904080986047999 691 38446306033680685734206979 692 40312772723361049383075650 693 42268440313695214272519055 694 44317505563774757494313126 695 46464359620275354243583208 696 48713596881831069253438142 697 51070024261391893236372922 698 53538670864166512954848391 699 56124798099500075511147254 700 58833910245854264405918642 701 61671765488871502373467493 702 64644387453390652353117830 703 67758077251170304426686828 704 71019426067038592531230036 705 74435328307152355307851158 706 78012995334097202547205748 707 81759969814609267995136161 708 85684140706835545401568822 709 89793758915193901284078776 710 94097453642128422825555769 711 98604249467297041164569910 712 103323584186072266363715937 713 108265327440586537095343606 714 113439800178009353828098968 715 118857794972215627172206392 716 124530597246586295329923508 717 130470007437278560488244984 718 136688364138024686337153060 719 143198568269254206911486462 720 150014108316199338379580584 721 157149086682534539206656419 722 164618247208126411952927783 723 172437003901521114949556263 724 180621470939999591807022796 725 189188493992260366930332693 726 198155682921176175480748310 727 207541445926498279887624723 728 217365025189973664566335704 729 227646534087971781987247244 730 238406996039535951884626191 731 249668385060633955724148233 732 261453668098434893180993071 733 273786849222551724371736085 734 286693015753501815375795399 735 300198386412011882065403818 736 314330361576395495686357893 737 329117575738895429186663855 738 344589952255784597737931521 739 360778760490005452987769873 740 377716675449360815834374358 741 395437840027589508732658989 742 413977929960260482023676800 743 433374221612109990591719105 744 453665662717428505288494739 745 474892946200204559341409837 746 497098587206137223266542366 747 520327003484156180080193609 748 544624599260959873411917318 749 570039852758080541962190915 750 596623407507343299467551206 751 624428167627106589045898485 752 653509397228565968838338083 753 683924824128467819553365319 754 715734748052067105846866947 755 749002153517827974818486401 756 783792827603473560404363234 757 820175482801317993942378727 758 858221885179603718813415635 759 898006988075587535627158739 760 939609071555661379772568843 761 983109887887576464609041337 762 1028594813280170988573077654 763 1076153006156626073172236887 764 1125877572238471608823353409 765 1177865736729071181233192624 766 1232219023897466843309339832 767 1289043444375940902185345639 768 1348449690497806564781618465 769 1410553340015482350184006655 770 1475475068553159182739440279 771 1543340871163035778320333210 772 1614282293369560685052543689 773 1688436672102015877635600904 774 1765947386932513858164577475 775 1846964122053729930098039395 776 1931643139448821934600826042 777 2020147563724665683633737719 778 2112647679099197280727406184 779 2209321239053889709325252452 780 2310353789183670557498520285 781 2415939003798537459648885795 782 2526279036854174091494686365 783 2641584887812630353155205677 784 2762076783059114786177446182 785 2887984573526685658052507730 786 3019548149207661401071975582 787 3157017871258479694992629786 788 3300655022434005130969639280 789 3450732276617489982317847621 790 3607534188244115340084642489 791 3771357702448749741915491003 792 3942512686802881662806434083 793 4121322485541136237111669950 794 4308124497214936504559499549 795 4503270776749233908534161166 796 4707128662918480506799025808 797 4920081432299549298775776709 798 5142528980802845511272573905 799 5374888533927854198643174834 800 5617595386936484910296789028