0 0 1 1 2 0 3 1 4 2 5 3 6 3 7 6 8 7 9 12 10 15 11 22 12 27 13 40 14 49 15 68 16 87 17 116 18 145 19 193 20 239 21 311 22 387 23 494 24 611 25 776 26 952 27 1193 28 1464 29 1817 30 2214 31 2733 32 3315 33 4060 34 4911 35 5974 36 7195 37 8713 38 10448 39 12585 40 15048 41 18039 42 21486 43 25660 44 30462 45 36231 46 42888 47 50820 48 59972 49 70843 50 83354 51 98143 52 115183 53 135212 54 158265 55 185287 56 216336 57 252596 58 294247 59 342701 60 398295 61 462813 62 536711 63 622232 64 720121 65 833066 66 962176 67 1110842 68 1280533 69 1475480 70 1697770 71 1952557 72 2242716 73 2574696 74 2952235 75 3383369 76 3873150 77 4431394 78 5064792 79 5785598 80 6602396 81 7530404 82 8580845 83 9772396 84 11119594 85 12645620 86 14368927 87 16318237 88 18517228 89 21001146 90 23800139 91 26957846 92 30512193 93 34517039 94 39020363 95 44088243 96 49781083 97 56180333 98 63361380 99 71424460 100 80463939 101 90602563 102 101958011 103 114681070 104 128917634 105 144852563 106 162666956 107 182586702 108 204835952 109 229691129 110 257428422 111 288385620 112 322903187 113 361392704 114 404272854 115 452045522 116 505223884 117 564419026 118 630259784 119 703488624 120 784874570 121 875319758 122 975762157 123 1087296531 124 1211066330 125 1348397524 126 1500681625 127 1669524314 128 1856615340 129 2063896658 130 2293418638 131 2547526267 132 2828703743 133 3139781251 134 3483763140 135 3864061313 136 4284306196 137 4748605142 138 5261339062 139 5827449469 140 6452214678 141 7141573209 142 7901878982 143 8740259795 144 9664354884 145 10682713183 146 11804506615 147 13039978161 148 14400130074 149 15897220898 150 17544433303 151 19356426866 152 21348977445 153 23539598608 154 25947152614 155 28592540630 156 31498291257 157 34689328737 158 38192530563 159 42037590827 160 46256547309 161 50884741816 162 55960325272 163 61525328211 164 67625134626 165 74309684980 166 81632921498 167 89654128571 168 98437360893 169 108052939751 170 118576855557 171 130092450454 172 142689800201 173 156467592488 174 171532505444 175 188001308188 176 206000228892 177 225667318371 178 247151818351 179 270616805492 180 296238584152 181 324209648924 182 354738099695 183 388050978955 184 424393727584 185 464033925848 186 507260827230 187 554389558368 188 605760736271 189 661745205047 190 722743769165 191 789192514950 192 861562714676 193 940366812872 194 1026158522362 195 1119539584724 196 1221160111987 197 1331726197085 198 1452000585165 199 1582811251690 200 1725052448221 201 1879694402755 202 2047784828658 203 2230459866799 204 2428946183665 205 2644573327042 206 2878776500299 207 3133110552479 208 3409253569302 209 3709022682476 210 4034378669688 211 4387443836565 212 4770507776010 213 5186047639619 214 5636735280097 215 6125460195677 216 6655338345596 217 7229738139754 218 7852291180434 219 8526921755778 220 9257859854464 221 10049674593886 222 10907289947585 223 11836022657358 224 12841601081988 225 13930208257340 226 15108504404028 227 16383675786713 228 17763461541579 229 19256209143548 230 20870906202727 231 22617243506916 232 24505652606963 233 26547377411540 234 28754518556923 235 31140114745564 236 33718194909692 237 36503870702223 238 39513397701756 239 42764280516589 240 46275344518401 241 50066855312021 242 54160602551997 243 58580035833795 244 63350362472382 245 68498701985683 246 74054200056833 247 80048204185448 248 86514396194889 249 93488992049729 250 101010895727201 251 109121926417622 252 117866997057397 253 127294372688634 254 137455877217714 255 148407187307241 256 160208071559960 257 172922724686567 258 186620043999371 259 201374009385372 260 217264002438586 261 234375238608755 262 252799135204259 263 272633802690260 264 293984468761753 265 316964036865392 266 341693574269787 267 368302947079979 268 396931381500038 269 427728185554132 270 460853394123385 271 496478589142217 272 534787640121347 273 575977636280455 274 620259736076131 275 667860226183448 276 719021495517584 277 774003238170475 278 833083569152850 279 896560390802564 280 964752670028041 281 1038001989888919 282 1116674010942566 283 1201160232805488 284 1291879664810708 285 1389280825780690 286 1493843652842479 287 1606081770895974 288 1726544672444128 289 1855820292639542 290 1994537496869551 291 2143369002134209 292 2303034214282942 293 2474302541260061 294 2657996627617820 295 2854996111401404 296 3066241309259718 297 3292737475655667 298 3535558999229004 299 3795854230006468 300 4074850255807769 301 4373858371956429 302 4694279514841021 303 5037610458443571 304 5405449992556382 305 5799505940568681 306 6221602181415818 307 6673686595560534 308 7157839041784652 309 7676280352208887 310 8231381389767935 311 8825673227707705 312 9461857429988411 313 10142817568353123 314 10871630885245524 315 11651581321229426 316 12486172740827908 317 13379143663989165 318 14334482258493927 319 15356442994094048 320 16449563629952291 321 17618684037882710 322 18868965442707775 323 20205911690883616 324 21635391034478539 325 23163660156595728 326 24797388825081419 327 26543687025368986 328 28410132851474889 329 30404803139313728 330 32536305008836089 331 34813810440302086 332 37247091931666012 333 39846561515469837 334 42623311053922938 335 45589156254162696 336 48756682188596390 337 52139292935703115 338 55751262984320956 339 59607793204672270 340 63725068877176982 341 68120322783174432 342 72811900690301762 343 77819332449722437 344 83163405870358880 345 88866246818070278 346 94951402525825104 347 101443931809577240 348 108370498989573089 349 115759475473858158 350 123641045606855287 351 132047321023407988 352 141012459901278340 353 150572795655987327 354 160766971253022509 355 171636084003915218 356 183223836791451228 357 195576700939567011 358 208744086428902328 359 222778525047240770 360 237735861922629236 361 253675461426121123 362 270660422625770867 363 288757810708990364 364 308038899272736668 365 328579430359488647 366 350459886846867208 367 373765784559884155 368 398587978408069482 369 425022990447532866 370 453173353847376957 371 483147981229856582 372 515062551031168701 373 549039920959698284 374 585210561851476057 375 623713021656604104 376 664694412491218323 377 708310931193624270 378 754728405944702735 379 804122880144206692 380 856681225713987580 381 912601797834293383 382 972095122876962045 383 1035384632416379273 384 1102707434666873821 385 1174315137163159410 386 1250474711603860070 387 1331469415687150514 388 1417599762412797147 389 1509184552768008592 390 1606561961820546508 391 1710090695302406240 392 1820151206245842133 393 1937146990017035440 394 2061505946833233313 395 2193681831466689521 396 2334155778745219734 397 2483437926009626637 398 2642069120656032961 399 2810622735501081488 400 2989706579607433173 401 3179964929007260446 402 3382080664478691128 403 3596777542639067087 404 3824822587030238102 405 4067028627438508168 406 4324256973645231773 407 4597420253984874595 408 4887485404448150530 409 5195476841003502177 410 5522479800432399072 411 5869643884841625037 412 6238186794721185044 413 6629398288399786333 414 7044644352379660836 415 7485371623300153144 416 7953112045661737697 417 8449487809203747287 418 8976216549755311002 419 9535116860851778503 420 10128114099691979879 421 10757246538396960312 422 11424671843968539589 423 12132673941891595317 424 12883670246672842617 425 13680219318571809382 426 14525028929819765420 427 15420964604242516050 428 16371058613696992903 429 17378519500301888696 430 18446742108106535003 431 19579318198666788670 432 20780047634572547570 433 22052950211336212926 434 23402278122261294496 435 24832529143161242307 436 26348460522311860084 437 27955103669517536690 438 29657779630686148873 439 31462115449390622040 440 33374061403086416712 441 35399909223732732247 442 37546311292048800093 443 39820300924136045751 444 42229313741620087034 445 44781210253792000843 446 47484299645212494626 447 50347364907877509337 448 53379689314143264847 449 56591084381056559799 450 59991919325539950240 451 63593152173624254411 452 67406362526988653047 453 71443786163678105265 454 75718351480683642761 455 80243717970142737551 456 85034316742003417337 457 90105393301103544227 458 95473052597462962544 459 101154306575405815705 460 107167124247140688965 461 113530484535662816278 462 120264431920463788851 463 127390135151870797310 464 134929949076478660734 465 142907479862374133576 466 151347653676827081916 467 160276789130093780093 468 169722673549647712428 469 179714643425671805482 470 190283669105329820601 471 201462444106347492555 472 213285479142343604003 473 225789201262847790190 474 239012058217341833430 475 252994628481610361550 476 267779737074794405900 477 283412577644064390382 478 299940840966742430876 479 317414850388974011795 480 335887704374924997868 481 355415426731652300448 482 376057124710738904510 483 397875155602188073050 484 420935302052052157512 485 445306956774300050901 486 471063316922483469654 487 498281588851793053856 488 527043203575206060286 489 557434043710038996016 490 589544682261216238109 491 623470634109412903410 492 659312620598021244629 493 697176848165618255929 494 737175301471038983074 495 779426052043645621341 496 824053582965125808543 497 871189130709365675807 498 920971044712767677487 499 973545165904289007423 500 1029065224841077583974 501 1087693260791415397473 502 1149600062492574494886 503 1214965632048297343583 504 1283979672784417008745 505 1356842102661868017656 506 1433763594166590699959 507 1514966142422858575348 508 1600683662561604453701 509 1691162618251440442273 510 1786662682548364102423 511 1887457433148179202117 512 1993835083335587047859 513 2106099250907037649046 514 2224569766514156976864 515 2349583523916146621726 516 2481495373757377208745 517 2620679063589816039391 518 2767528225944071823705 519 2922457417421903337199 520 3085903210821491994992 521 3258325343545501505156 522 3440207924532857348271 523 3632060703267643341901 524 3834420403359946353506 525 4047852124584250949387 526 4272950816150771610175 527 4510342825459007345899 528 4760687525418950869340 529 5024679024987331429547 530 5303047966346715489855 531 5596563413810773264176 532 5906034838261447650603 533 6232314202678585519621 534 6576298152984907203701 535 6938930320289302936305 536 7321203739211490478018 537 7724163388943083348053 538 8148908862235479299238 539 8596597169595897613721 540 9068445684441419566345 541 9565735237177917871822 542 10089813364570260165142 543 10642097723121304631874 544 11224079673505230905282 545 11837328045594455062418 546 12483493091873806586827 547 13164310639680677727289 548 13881606450888555165505 549 14637300800457382146284 550 15433413283374790830939 551 16272067862489564211661 552 17155498167759196744841 553 18086053060592683500524 554 19066202474908155606313 555 20098543549877938788609 556 21185807067187919937060 557 22330864209197264494245 558 23536733652153002515191 559 24806589012392370643487 560 26143766661146887259718 561 27551773927574043290353 562 29034297707234472257114 563 30595213497493153073418 564 32238594878824983307378 565 33968723465530464290719 566 35790099346777934806117 567 37707452043696407632585 568 39725752005561680981705 569 41850222673226884348905 570 44086353135174974033576 571 46439911406999601112482 572 48916958362255012863235 573 51523862348386419917917 574 54267314518494541832842 575 57154344915823566836780 576 60192339344813268117920 577 63389057069080354028401 578 66752649373556556597793 579 70291679034950458852745 580 74015140741475282001690 581 77932482510167672055429 582 82053628146813720413621 583 86389000801354281353090 584 90949547668252757595689 585 95746765889669833208287 586 100792729715825002662481 587 106100118985826275783100 588 111682248988715094018040 589 117553101773951974673130 590 123727358976971456043925 591 130220436235530467816542 592 137048519268922552317776 593 144228601702885964772843 594 151778524719337224422723 595 159717018621522890500741 596 168063746401452655653286 597 176839349408693356484031 598 186065495215853293473753 599 195764927789111371197821 600 205961520068390306932906 601 216680329075663511854628 602 227947653666142525063229 603 239791095051909208678264 604 252239620223846080544928 605 265323628413528739045324 606 279075020733088318222650 607 293527273147926293847403 608 308715512933588586750670 609 324676598786120956754179 610 341449204751761325006462 611 359073908161062968733023 612 377593281749218175347415 613 397051990164901608610780 614 417496891066807187041565 615 438977141029009203343786 616 461544306473352376513637 617 485252479870542873154080 618 510158401448952158044798 619 536321586675233520341515 620 563804459768508518955766 621 592672493536709135132270 622 622994355821693099211452 623 654842062868448046602142 624 688291139932170480766786 625 723420789467711514865148 626 760314067244861708297473 627 799058066765811339804468 628 839744112360691028486489 629 882467961372281507259384 630 927330015841226216844302 631 974435544140757615995757 632 1023894913010966621909239 633 1075823830483003683730732 634 1130343600185498743174665 635 1187581387568731517385554 636 1247670498584981815286990 637 1310750671409836996501068 638 1376968381793263016791556 639 1446477162678933078491140 640 1519437938735612169392453 641 1596019376497679123765055 642 1676398250818607276616026 643 1760759828398378553984293 644 1849298269154156755065271 645 1942217046264868230552821 646 2039729385730493241544763 647 2142058726352684292038106 648 2249439201055500734353366 649 2362116140535698743646544 650 2480346600246441436969914 651 2604399911794156361173712 652 2734558259845202309700336 653 2871117285720488361941376 654 3014386718875915301263758 655 3164691037554045900486705 656 3322370159915241160360024 657 3487780167050565494427645 658 3661294059305037005062301 659 3843302547440906663927822 660 4034214880200739933913494 661 4234459709938775646026180 662 4444485998023352756270996 663 4664763961830089236751773 664 4895786065184485917238974 665 5138068054238361040647756 666 5392150040808673928852192 667 5658597635342565948033845 668 5938003131722300962077280 669 6230986746269350722838287 670 6538197913363011680253033 671 6860316640245614209987709 672 7198054923649456254393092 673 7552158231049261352436754 674 7923407049414664320925008 675 8312618504518846017194651 676 8720648053938539296456221 677 9148391257076230944506322 678 9596785625623720896587591 679 10066812558096903548863374 680 10559499362170123365957992 681 11075921368765471665291558 682 11617204141962025977874561 683 12184525789034667994441618 684 12779119375053987855579028 685 13402275446742450190493780 686 14055344670417294903286006 687 14739740589134878184562331 688 15456942504301176114207510 689 16208498487319627101791462 690 16996028527013639016142326 691 17821227818891551381028291 692 18685870202505665253185161 693 19591811753513367706053540 694 20540994537251547596128890 695 21535450531019960676059557 696 22577305722493547483826149 697 23668784392098481783787880 698 24812213587434238560277053 699 26010027798271513074822776 700 27264773840928663207844272 701 28579115961312313622867625 702 29955841166208289581309038 703 31397864792930308050703238 704 32908236327764638247565096 705 34490145484211605929137944 706 36146928552388644363838773 707 37882075031567022209065718 708 39699234558214289303723665 709 41602224142570308190269962 710 43595035727224035379350221 711 45681844081866379191408767 712 47867015048876730354442301 713 50155114155165518405562180 714 52550915606224294384120647 715 55059411679160793672604113 716 57685822532076701776556472 717 60435606448037979785924136 718 63314470532523603536631735 719 66328381884202276070624776 720 69483579259583408989170128 721 72786585253129773018174373 722 76244219015182134534802421 723 79863609531171008154507514 724 83652209486425657697275327 725 87617809742105824186075434 726 91768554448695165728683546 727 96112956824808650549127476 728 100659915630065121830185946 729 105418732362195405182083725 730 110399129209648335960822831 731 115611267792490768275925353 732 121065768725590871907581137 733 126773732039731576692853924 734 132746758497604413245776348 735 138996971843425525366197785 736 145537042026338821991167771 737 152380209439707663483280121 738 159540310219949956998395533 739 167031802650664675081919228 740 174869794719492949670500319 741 183070072877419526891415378 742 191649132052069489337079079 743 200624206969001100293346907 744 210013304837012100967646333 745 219835239456120993123074848 746 230109666809083167761946493 747 240857122200160357065166908 748 252099059007257774400300049 749 263857889116633812906393822 750 276157025111997653415547042 751 289020924293151413560823527 752 302475134602177000861359720 753 316546342538780316926688737 754 331262423149502034980098538 755 346652492179409944165435453 756 362746960478259143778852663 757 379577590757329295080367806 758 397177556796817616744217577 759 415581505208232196925161659 760 434825619860223280214941410 761 454947689081226934248608870 762 475987175756639731028544542 763 497985290443580829877930233 764 520985067631023043341342422 765 545031445278845817643358580 766 570171347774501495854268359 767 596453772452226405199489100 768 623929879825314944199774935 769 652653087688721900664583152 770 682679169255330901055759299 771 714066355496521969352130853 772 746875441864270822942421392 773 781169899579900087569547401 774 817015991681773566296920705 775 854482894032752754084010247 776 893642821496025007687508534 777 934571159497133241795739710 778 977346601198498389635908976 779 1022051290522694806449301418 780 1068770971269927455531879563 781 1117595142585937705038468459 782 1168617221046541252053744068 783 1221934709636654172872013808 784 1277649373912493493778097037 785 1335867425648236346763541739 786 1396699714280176925341059473 787 1460261926475039662090136796 788 1526674794161863785816844913 789 1596064311381597636839737499 790 1668561960322382504516584406 791 1744304946924422061640845475 792 1823436446453349327550880847 793 1906105859458208677280507479 794 1992469078546457844867881368 795 2082688766426993614191661622 796 2176934645689868845260456316 797 2275383800811472563277042637 798 2378220992893098768258743730 799 2485638987662560142957099793 800 2597838897289269353488324995 801 2715030536586698371065676966 802 2837432794198637829006329724 803 2965274019391064559050186256 804 3098792425095825275929770688 805 3238236507879781301450132824 806 3383865485539501965489932674 807 3535949753051246562461314334 808 3694771357634627500262345157 809 3860624493720392425668846998 810 4033816018643806395826631594 811 4214665989919744876634421302 812 4403508224989237136414399632 813 4600690884364620747932107666 814 4806577079136892760441560248 815 5021545503849278929204109875 816 5245991095780490707457525354 817 5480325721724831104704269299 818 5724978893399027857802391806 819 5980398512652879288447686342 820 6247051647707049701755960646 821 6525425341692354116750382921 822 6816027454814943984820131841 823 7119387541526907088337862228 824 7436057764135996067134098836 825 7766613844347726624113114710 826 8111656054291750637173950567 827 8471810248648713250145379276 828 8847728939557290127363618522 829 9240092416050562007042940081 830 9649609909839582275913573676 831 10077020809337021092906815634 832 10523095923888098920873206490 833 10988638800257058911343031701 834 11474487093497840102334614437 835 11981513994425135333675144510 836 12510629715989001643267407778 837 13062783040950712175714986882 838 13638962933351620473757187515 839 14240200216368882827252785264 840 14867569319253632325625405263 841 15522190096157424151592690188 842 16205229719762798609932295729 843 16917904652752829657534636887 844 17661482700273493635248876913 845 18437285146671204160644868974 846 19246688979916478970627470571 847 20091129207263454521454908814 848 20972101265834005695518175993 849 21891163531965023917423368628 850 22849939933307699243197721325 851 23850122667829363903750386434 852 24893475034030891668090323561 853 25981834376867212964459014990 854 27117115154034050963530799247 855 28301312127472413670277400878 856 29536503685132069682169517134 857 30824855298238618473347645514 858 32168623119513726038856852021 859 33570157728017606847168230541 860 35031908026504267640535870797 861 36556425297416930203291722152 862 38146367423890260579094682721 863 39804503282381687736011177433 864 41533717313812483131026776003 865 43337014280375149921972142916 866 45217524215442748307894668935 867 47178507574313463887613874693 868 49223360593825121289372821247 869 51355620869195532278397574585 870 53578973156770035084824003204 871 55897255411704109997713163598 872 58314465069960386292204076567 873 60834765584373201470069744584 874 63462493224913302702727123873 875 66202164153688572309865105285 876 69058481785626280607103932162 877 72036344446217399539289559296 878 75140853338145687525042444176 879 78377320829093492472362220129 880 81751279073493497398412575776 881 85268488981501733890964926277 882 88934949548982307497012679978 883 92756907562840105845235750815 884 96740867696593672198616267504 885 100893603011669060772539412780 886 105222165880495373438929346216 887 109733899348117434872465951031 888 114436448949688340179539959320 889 119337775001889060817850481433 890 124446165387020649933055748231 891 129770248849252577781863130719 892 135319008823264128304063348241 893 141101797816311452085981335964 894 147128352365565586674815757441 895 153408808593424546358201491817 896 159953718384379211132554115241 897 166774066207937454387273672532 898 173881286613056435753141710909 899 181287282420529770463716517539 900 189004443640795957604327186133 901 197045667145708858196673641783 902 205424377123910599651537982603 903 214154546350605285626102596198 904 223250718303717556995673268103 905 232728030159668069557603305200 906 242602236703276337300716300195 907 252889735187646337970970553376 908 263607591181268516859178200225 909 274773565441021134910636630421 910 286406141851239683535281513969 911 298524556470584758001921073361 912 311148827730040358094722731416 913 324299787827057215346713293020 914 337999115362582012661626543135 915 352269369269526205727724995611 916 367134024083088673425508929752 917 382617506605299431192672143221 918 398745234018156694730639012343 919 415543653501833451928881187501 920 433040283416590350722708359420 921 451263756109297951729629417764 922 470243862407799535778192840775 923 490011597868786641307575547484 924 510599210847367930749618731463 925 532040252459141017164115872591 926 554369628508279343752894847847 927 577623653457977591575871500728 928 601840106522510378055600771253 929 627058289963208119023895783172 930 653319089673789940140459577222 931 680665038143776891225094646139 932 709140379892086549267830619859 933 738791139466445489880607865943 934 769665192107894133347798082903 935 801812337183464990588293268092 936 835284374494033306597936363634 937 870135183568437270420152137510 938 906420806059184108750012748355 939 944199531359470265155579206217 940 983531985565787007974476515255 941 1024481223915132116169397141631 942 1067112826830739948268127900400 943 1111494999715354403135095035343 944 1157698676636335803656548951941 945 1205797628052395209932678432741 946 1255868572737419373702768559792 947 1307991294062771705516012260995 948 1362248760805557939668598596172 949 1418727252656718625881636331188 950 1477516490609380188239605974157 951 1538709772414754968217944431125 952 1602404113299951698042351451981 953 1668700392149438227809017303710 954 1737703503359508505532567912771 955 1809522514583047060754718426447 956 1884270830590074092439039099476 957 1962066363478098464144870201529 958 2043031709475118966341648252125 959 2127294332587306550568626304280 960 2214986755352883260573087434973 961 2306246756973602607509169748619 962 2401217579105439336815012396097 963 2500048139600734355012639763928 964 2602893254505017894060991169163 965 2709913868623176580237390245043 966 2821277294981439404708583976690 967 2937157463523965049829225759336 968 3057735179395516561379316152707 969 3183198391174946209824289506381 970 3313742469437877895219538762720 971 3449570496041209979355935644698 972 3590893564536758602927328003943 973 3737931092136670127506244257957 974 3890911143669038141277641576985 975 4050070767978621946645785499389 976 4215656347244562492181933979344 977 4387923959704691795417675735193 978 4567139756294311881333275634217 979 4753580351726349946427585734975 980 4947533230559452567539530826014 981 5149297168821041800879179387398 982 5359182671773490433101368985237 983 5577512428433568985857213566489 984 5804621783478039459304230831805 985 6040859227191915179443656227030 986 6286586904140334151553016376553 987 6542181141270408782434521288736 988 6808032996175674815066541153574 989 7084548826283079816564443609109 990 7372150879750679000383907902919 991 7671277908893566210722045998885 992 7982385806985908202249395644136 993 8305948269318503703698388730939 994 8642457479423897932544295294406 995 8992424821414991633357343585399 996 9356381619418129138711024133332 997 9734879905118086920850569815474 998 10128493214470045332755469546301 999 10537817414672777903174589667526 1000 10963471562537762198588896679697