0 0 1 0 2 1 3 0 4 1 5 1 6 3 7 3 8 5 9 6 10 10 11 12 12 19 13 23 14 34 15 41 16 58 17 72 18 98 19 121 20 162 21 200 22 262 23 323 24 415 25 511 26 650 27 796 28 1000 29 1222 30 1522 31 1851 32 2287 33 2771 34 3399 35 4103 36 5000 37 6015 38 7289 39 8735 40 10530 41 12579 42 15094 43 17968 44 21468 45 25477 46 30319 47 35873 48 42531 49 50177 50 59291 51 69753 52 82158 53 96402 54 113207 55 132494 56 155155 57 181148 58 211566 59 246434 60 287091 61 333660 62 387788 63 449717 64 521486 65 603530 66 698338 67 806600 68 931392 69 1073736 70 1237423 71 1423925 72 1637910 73 1881445 74 2160292 75 2477272 76 2839501 77 3250811 78 3719950 79 4252043 80 4857896 81 5544266 82 6324481 83 7207393 84 8209427 85 9342106 86 10625675 87 12074987 88 13715000 89 15564813 90 17655123 91 20010325 92 22668228 93 25659824 94 29031618 95 32822864 96 37090695 97 41884642 98 47274873 99 53323602 100 60116967 101 67732928 102 76277047 103 85846696 104 96571231 105 108571892 106 122006990 107 137027145 108 153825887 109 172589882 110 193555544 111 216953556 112 243072457 113 272196822 114 304678330 115 340867265 116 381191959 117 426082656 118 476060445 119 531652869 120 593493160 121 662226978 122 738623109 123 823470251 124 917700830 125 1022276837 126 1138327789 127 1267025100 128 1409735824 129 1567884075 130 1743122608 131 1937180266 132 2152053061 133 2389836734 134 2652939488 135 2943898080 136 3265615070 137 3621157097 138 4014018770 139 4447902323 140 4927011254 141 5455809228 142 6039347279 143 6683000586 144 7392832489 145 8175307997 146 9037698663 147 9987770825 148 11034236624 149 12186415263 150 13454734552 151 14850364352 152 16385774611 153 18074338456 154 19930953809 155 21971614787 156 24214103368 157 26677528296 158 29383094802 159 32353609016 160 35614335715 161 39192466935 162 43118076906 163 47423555038 164 52144669639 165 57319963470 166 62991939857 167 69206421019 168 76013869936 169 83468712725 170 91630812362 171 100564755115 172 110341495749 173 121037609677 174 132737128709 175 145530763340 176 159517952352 177 174806057735 178 191512655404 179 209764708741 180 229701128503 181 251471933454 182 275241112804 183 301185781976 184 329499387022 185 360390867315 186 394088242427 187 430837798940 188 470908108219 189 514589253616 190 562197335366 191 614073761335 192 670590299024 193 732148459160 194 799185164843 195 872172259450 196 951622874764 197 1038091103278 198 1132179152655 199 1234537233398 200 1345871602357 201 1466944719917 202 1598584301157 203 1741683811234 204 1897212653528 205 2066217086129 206 2249831696681 207 2449280832600 208 2665891536152 209 2901095600100 210 3156444152932 211 3433610475037 212 3734406454887 213 4060786315440 214 4414865194758 215 4798923963488 216 5215430210751 217 5667044366166 218 6156643414545 219 6687328563592 220 7262452059942 221 7885626686746 222 8560756095074 223 9292046466849 224 10084040838774 225 10941633308347 226 11870107896369 227 12875155741238 228 13962919111555 229 15140012106602 230 16413570520188 231 17791276635605 232 19281415744406 233 20892905720130 234 22635361092713 235 24519128197077 236 26555357835758 237 28756046904403 238 31134120821640 239 33703482679183 240 36479106766511 241 39477096454077 242 42714790329886 243 46210830190700 244 49985281522554 245 54059713185281 246 58457334187858 247 63203086893775 248 68323802319293 249 73848308933933 250 79807609019608 251 86235005454102 252 93166301997013 253 100639950794582 254 108697279857110 255 117382664398936 256 126743785224239 257 136831827470657 258 147701774100155 259 159412636133509 260 172027786024245 261 185615224022852 262 200247956864402 263 216004305571038 264 232968335590852 265 251230212098587 266 270886688560075 267 292041516412827 268 314805999977645 269 339299468368658 270 365649905702471 271 393994494187242 272 424480329792612 273 457265046665520 274 492517629787448 275 530419132277365 276 571163598062339 277 614958885216905 278 662027713416272 279 712608608217733 280 766957090034801 281 825346756301820 282 888070630875579 283 955442403329811 284 1027797960202198 285 1105496803208822 286 1188923786579412 287 1278490738928407 288 1374638434055412 289 1477838444523463 290 1588595376900441 291 1707448988783267 292 1834976723514321 293 1971796126617795 294 2118567719527364 295 2275997756175092 296 2444841480423890 297 2625906268853764 298 2820055322392525 299 3028211247417785 300 3251360238542053 301 3490556156978370 302 3746925268796808 303 4021670887127526 304 4316078738490397 305 4631522244083655 306 4969468596019717 307 5331484762720157 308 5719244367385544 309 6134534513414171 310 6579263569223826 311 7055468921994576 312 7565325786127881 313 8111156007524742 314 8695438027876921 315 9320816877245834 316 9990115443135612 317 10706345806735635 318 11472721984432578 319 12292672782862330 320 13169856201670097 321 14108174004613609 322 15111787996115681 323 16185136530636327 324 17332952902089873 325 18560284041725237 326 19872511289392672 327 21275371561512359 328 22774980806738156 329 24377857960909528 330 26090951427157157 331 27921666174361224 332 29877893623973190 333 31968042292785906 334 34201071516068075 335 36586526085304919 336 39134574290132585 337 41856047057565331 338 44762480854665599 339 47866161898221210 340 51180174526682494 341 54718451119403986 342 58495826620774213 343 62528094886720479 344 66832070127481075 345 71425650486858325 346 76327887263553494 347 81559056627183013 348 87140737582510320 349 93095892836476473 350 99448956586717198 351 106225925677010833 352 113454458422397034 353 121163977328442968 354 129385780311449660 355 138153156411272350 356 147501510928806871 357 157468495734386300 358 168094150027687361 359 179421047036617309 360 191494452308970967 361 204362488812228928 362 218076314894710370 363 232690310037222121 364 248262274876562854 365 264853640128905865 366 282529691353069524 367 301359803865838866 368 321417695240459455 369 342781689369033824 370 365535000046625206 371 389766027710083894 372 415568677853883673 373 443042694392243542 374 472294017094670096 375 503435155983685035 376 536585592470843498 377 571872199721873108 378 609429692723052200 379 649401100124825340 380 691938269081043034 381 737202394727434815 382 785364586318956302 383 836606461219221980 384 891120779621588283 385 949112110727531557 386 1010797544184672429 387 1076407437024981994 388 1146186210896966368 389 1220393189329528728 390 1299303490886246576 391 1383208967428583949 392 1472419204490531376 393 1567262572447652432 394 1668087346712934811 395 1775262885090875249 396 1889180881844408604 397 2010256686040637059 398 2138930705151429669 399 2275669880896125105 400 2420969259832243758 401 2575353645090521763 402 2739379353406472452 403 2913636063244849255 404 3098748779940858449 405 3295379903047134988 406 3504231423718941909 407 3726047236714064804 408 3961615596895825585 409 4211771704202584398 410 4477400449187096809 411 4759439302478506380 412 5058881382658914075 413 5376778685303045001 414 5714245510248796359 415 6072462069256026197 416 6452678313899458090 417 6856217965280091618 418 7284482788400123357 419 7738957092237223729 420 8221212501601001803 421 8732912981292983748 422 9275820162149115935 423 9851798949013710442 424 10462823464002304536 425 11110983304681551371 426 11798490174607552461 427 12527684865495248571 428 13301044652875184910 429 14121191084232221154 430 14990898226259282816 431 15913101350034342869 432 16890906125922598973 433 17927598306936430861 434 19026653977949541539 435 20191750349551032464 436 21426777179995521252 437 22735848804237579122 438 24123316860071301786 439 25593783690741914211 440 27152116521163593138 441 28803462387690976090 442 30553263926292130135 443 32407275999882500482 444 34371583278033371519 445 36452618750894800212 446 38657183299621890685 447 40992466306530059432 448 43466067437119759560 449 46086019578928849363 450 48860813080049347980 451 51799421274397039580 452 54911327448186763237 453 58206553237281491494 454 61695688622490897387 455 65389923515574755352 456 69301081116746176348 457 73441653040094455283 458 77824836402637152644 459 82464572877734753859 460 87375589924800571653 461 92573444201082440986 462 98074567385098487059 463 103896314423371342468 464 110057014449249000024 465 116576024392248266601 466 123473785547619076389 467 130771883132391851092 468 138493109120375539927 469 146661528391358215527 470 155302548511777343325 471 164442993192400784654 472 174111179767308316240 473 184337000751454770023 474 195152009850554815447 475 206589512493935847228 476 218684661296201149701 477 231474556533525748708 478 244998352075434100710 479 259297366875074560252 480 274415202497020244170 481 290397866805055395622 482 307293904330626205301 483 325154533466362435093 484 344033791050797970864 485 363988684513425634739 486 385079352195817173444 487 407369232045770667621 488 430925239354360827272 489 455817953764118699458 490 482121816277336611442 491 509915336527802394833 492 539281311109519988353 493 570307053265034864336 494 603084634797434346294 495 637711140552649476976 496 674288936413161788846 497 712925951198948461691 498 753735973500934850301 499 796838963897759980385 500 842361383673093108056 501 890436540545656863307 502 941204952629713615973 503 994814731206574532089 504 1051421983634760165541 505 1111191237055585692940 506 1174295884341907881262 507 1240918653031649416781 508 1311252098825159535253 509 1385499124482400764094 510 1463873525842613408352 511 1546600565907359368008 512 1633917578866619095960 513 1726074605125384594975 514 1823335059382155900336 515 1925976432946157458774 516 2034291032532514939000 517 2148586756865750331193 518 2269187913536289975275 519 2396436077599505286192 520 2530690994586735526546 521 2672331529594192427906 522 2821756665365073608875 523 2979386551226153433010 524 3145663606063174589420 525 3321053677412593756819 526 3506047260148320500750 527 3701160777080321754418 528 3906937925265755966281 529 4123951090614204778654 530 4352802834940017744865 531 4594127458335961793455 532 4848592641406750001177 533 5116901170559995799075 534 5399792751315066308541 535 5698045913184559418445 536 6012480011550546208541 537 6343957330484677543564 538 6693385292439504033479 539 7061718779195378645325 540 7449962570543140176294 541 7859173905567191482527 542 8290465173614150569096 543 8745006740341354451215 544 9224029916592435588030 545 9728830076078215218127 546 10260769930334604949287 547 10821282967579391504891 548 11411877064732369353823 549 12034138279929847693038 550 12689734835665516540882 551 13380421300669788238676 552 14108042981608883643628 553 14874540533575860937839 554 15681954801493580855930 555 16532431902348575614982 556 17428228561512395348467 557 18371717714111285741725 558 19365394385944374443516 559 20411881866057479358438 560 21513938186833366374156 561 22674462924966300815613 562 23896504340670398333324 563 25183266869875878363060 564 26538118988391397422420 565 27964601464310479281688 566 29466436019421961413403 567 31047534417577276610465 568 32712008002723619137683 569 34464177706395982338524 570 36308584549509238049983 571 38250000660264647515963 572 40293440835344131663945 573 42444174668426641018399 574 44707739275750798951654 575 47089952645195590927842 576 49596927641393133820240 577 52235086696020946814041 578 55011177218838832497847 579 57932287761554275935692 580 61005864973418034077234 581 64239731383855872535914 582 67642104054686631649604 583 71221614140767249704885 584 74987327405604263488421 585 78948765734649221326383 586 83115929697179263636585 587 87499322203731496985114 588 92109973314760948807164 589 96959466252151568374327 590 102059964674462935957016 591 107424241272651094791851 592 113065707752844397230508 593 118998446268511839126948 594 125237242374833048409936 595 131797619573742477028182 596 138695875529264038749993 597 145949120028329885993567 598 153575314774138681878304 599 161593315094608911985870 600 170022913661111742891959 601 178884886308101212334625 602 188201040057708705177073 603 197994263448747190688432 604 208288579283896953277320 605 219109199904182423461841 606 230482585115114154507714 607 242436502884183626487619 608 255000092945666765141116 609 268203933444000342554640 610 282080110764337960799201 611 296662292694216809585603 612 311985805078759100634986 613 328087712127197460769124 614 345006900548237953990923 615 362784167687208706387759 616 381462313858985910989160 617 401086239066223900194293 618 421703044314873579891710 619 443362137734644897475791 620 466115345736041927301699 621 490017029431447378230819 622 515124206573330887063201 623 541496679258725809242378 624 569197167676459137488269 625 598291450169962508841570 626 628848509917701224639334 627 660940688529931403875691 628 694643846891709946733913 629 730037533579148487277312 630 767205161209269762965438 631 806234191081355464201937 632 847216326503352990829973 633 890247715194982139092206 634 935429161197343072493707 635 982866346717531015966162 636 1032670064377589572634705 637 1084956460336566412120201 638 1139847288798126140614836 639 1197470178416442611669771 640 1257958911159862742486635 641 1321453714193056269796770 642 1388101565388445390199726 643 1458056513080017641309690 644 1531480010726263642392516 645 1608541267152523767827919 646 1689417613100493674502918 647 1774294884817575194334811 648 1863367825480342622648019 649 1956840505252903000825920 650 2054926760846943153448817 651 2157850655458532792846266 652 2265846960027535774129285 653 2379161656775741878708860 654 2498052466055747731390364 655 2622789397555097092183044 656 2753655326981634257038545 657 2890946599370988571790122 658 3034973660244504234601759 659 3186061715863663511628665 660 3344551423920859763001567 661 3510799616027195748111440 662 3685180053458699149253899 663 3868084217646597695879741 664 4059922137005457003885779 665 4261123251721045783806657 666 4472137318235977186254186 667 4693435355203464232564363 668 4925510632804360336494274 669 5168879707359629229940694 670 5424083503304546744027701 671 5691688444633094209166769 672 5972287638065217102827097 673 6266502110237511391025840 674 6574982101372959078530093 675 6898408417939553962132730 676 7237493846974416336325868 677 7592984634811200800611329 678 7965662033127980270527489 679 8356343915301697327701880 680 8765886466248271226557947 681 9195185949004842910610890 682 9645180551518333858603667 683 10116852317191230351638877 684 10611229162959059972771088 685 11129386988771039534076725 686 11672451882586050470002736 687 12241602425104407435173345 688 12838072098715046743715725 689 13463151805258482156132055 690 14118192497484993604809552 691 14804607929221862068391729 692 15523877529564131774517463 693 16277549406552681159590699 694 17067243486127324398964789 695 17894654792308363750630610 696 18761556874909088449164664 697 19669805391265388575709089 698 20621341848844877053682370 699 21618197515801277441571523 700 22662497506945387595197396 701 23756465052828856669874479 702 24902425960074248908896122 703 26102813271333396187028814 704 27360172133727508448850984 705 28677164884896860291517758 706 30056576366296325887676156 707 31501319473675620091136314 708 33014440955231524460762086 709 34599127468252828933251554 710 36258711905670330573783712 711 37996680004291410710785202 712 39816677247136998226504386 713 41722516072702747242009731 714 43718183404654989821123587 715 45807848515916271220429510 716 47995871241838530754976838 717 50286810557650146415477781 718 52685433536165250095552661 719 55196724702279785857697039 720 57825895801644675062748407 721 60578396001494778977566667 722 63459922542547101479071074 723 66476431861526990480575140 724 69634151204890288020124776 725 72939590755016820868615058 726 76399556291240287376417246 727 80021162408854744557112834 728 83811846320414560186344157 729 87779382264493610247731885 730 91931896548340215953819901 731 96277883251793578607101823 732 100826220621199868258696050 733 105586188183082880422290893 734 110567484608806507995042760 735 115780246362578284978330953 736 121235067166744449987386937 737 126943018319542656570196451 738 132915669902208156332939683 739 139165112913657765368375408 740 145703982372844564239124104 741 152545481430327483965717451 742 159703406532618792695757664 743 167192173684457170074588936 744 175026845856335339190030688 745 183223161586341031561830309 746 191797564827726952334677566 747 200767236095512999982377002 748 210150124967970754537079737 749 219964984000899331275856146 750 230231404115353740392282902 751 240969851521732340779163355 752 252201706246103968810987245 753 263949302327103253070112021 754 276235969754936584296412967 755 289086078226709090938329686 756 302525082795756370093803634 757 316579571495571486972006441 758 331277315022671647868566460 759 346647318565915109913885206 760 362719875873836030192052849 761 379526625655012732789338998 762 397100610410869853765013764 763 415476337804068291267799589 764 434689844670376292691471035 765 454778763786000243534372925 766 475782393507476278679384547 767 497741770405669072179394723 768 520699745020960915208700220 769 544701060871550006646034578 770 569792436852761380776046935 771 596022653170533396284754906 772 623442640958711210310720043 773 652105575735497684048873393 774 682066974861403837850306992 775 713384799167258312894303583 776 746119558928392463454606022 777 780334424367875345523058621 778 816095340879841257712232810 779 853471149171295870557133804 780 892533710529615995517267632 781 933358037430936328583760122 782 976022429714159511077754041 783 1020608616553992230149077560 784 1067201904476724731698398687 785 1115891331671883138356481827 786 1166769828864032529475543231 787 1219934387019228645198963675 788 1275486232172665814070308434 789 1333531007675163816237152580 790 1394178964169159948324325542 791 1457545157616915680882373549 792 1523749655717723123294978779 793 1592917753063966375375841418 794 1665180195401105660753531237 795 1740673413370833862237800525 796 1819539766133096375148664978 797 1901927795278050804393795092 798 1987992489456811593958896969 799 2077895560176513650317435641 800 2171805729224431512482260299 801 2269899028203990481364865971 802 2372359110686257698860583522 803 2479377577500128121899912914 804 2591154315706845323850135873 805 2707897851825776687921805837 806 2829825719902595161320591544 807 2957164845034087747183834155 808 3090151942989996003938657500 809 3229033936597296820036852269 810 3374068389580625684622946299 811 3525523958579641057591410006 812 3683680864094700027592149478 813 3848831381141576317505259200 814 4021280350428983062608114526 815 4201345710904472958969604413 816 4389359054549976095282061612 817 4585666204342694860496618173 818 4790627816335631502929555547 819 5004620006849347462027234147 820 5228035005808207128817136817 821 5461281837294779468764685878 822 5704787028441068784640727807 823 5958995347819015232221289234 824 6224370574541314294207138375 825 6501396299330993648362863592 826 6790576758870692650248005011 827 7092437704793891692905876693 828 7407527308737053761955482332 829 7736417104927171542823940156 830 8079702971840471240680594295 831 8438006154528125577814673798 832 8811974329270989756020112673 833 9202282712290414051857869916 834 9609635214313640660238941040 835 10034765642862668320251210556 836 10478438954212634465772296205 837 10941452557041905481427932992 838 11424637669879396650242739583 839 11928860734537011879517354373 840 12455024887805077074812603977 841 13004071493777736432505166294 842 13576981739272443646428024547 843 14174778294904040888577141654 844 14798527044478827392539688059 845 15449338885478226732010218802 846 16128371603514928711594620945 847 16836831823757062042264688771 848 17575977042438237993070536003 849 18347117741693134235207960942 850 19151619591090300053190000009 851 19990905739365570653599481886 852 20866459200001984305471802692 853 21779825334444465973023346677 854 22732614436891366870777058463 855 23726504424758829983931955109 856 24763243639079987052167563128 857 25844653759267297337189759223 858 26972632836845542679291289435 859 28149158452942707209196972478 860 29376291004519376460577555099 861 30656177124511475141347605107 862 31991053241269884985966157096 863 33383249282890283564025678179 864 34835192532251782714932855576 865 36349411638809592981801463547 866 37928540793429986534493140724 867 39575324072800656173016241212 868 41292619960211815076611939910 869 43083406049767816780571836705 870 44950783941372023094939025044 871 46897984334113235591532657195 872 48928372325987271639448176913 873 51045452928195669898058486642 874 53252876802592833200528653565 875 55554446231185928285489081111 876 57954121326947117137721978636 877 60456026495557243867895047361 878 63064457158083307500593814758 879 65783886744980216910338762319 880 68618973972220655785581241070 881 71574570410775907467152817226 882 74655728361116287393626763346 883 77867709044852120870288910630 884 81215991126116988687446710585 885 84706279575783118655190095466 886 88344514892117286773234649117 887 92136882692012410081334581777 888 96089823687489121505785633662 889 100210044062730110180256736513 890 104504526267512886946924296388 891 108980540243520045866147006420 892 113645655100656122538865899521 893 118507751261161970789461175774 894 123575033090018407356795291279 895 128856042030844863583006916359 896 134359670267254331759635859343 897 140095174930396098185443244915 898 146072192874232245691473467100 899 152300756040924683432277478173 900 158791307439587437438390428142 901 165554717762554969138658500778 902 172602302664263638376524430639 903 179945840728809765274995010042 904 187597592153267728485985085721 905 195570318174893609034925271000 906 203877301271439165755788207297 907 212532366164924576696967944570 908 221549901660403040429441536245 909 230944883352461843266157759127 910 240732897233481091468839015248 911 250930164238977447657889369830 912 261553565766735784080547809334 913 272620670207839711094173232810 914 284149760529194073065199502248 915 296159862948650284143748274191 916 308670776745442223646822312398 917 321703105250276347286202575338 918 335278288061139999930734666456 919 349418634532655066961417510072 920 364147358588657343269170373721 921 379488614909582108220874465305 922 395467536548232690680508669436 923 412110274029556353793273920313 924 429444035992202083747365653091 925 447497131431841117267996965027 926 466299013608546981321642865227 927 485880325682908891412442637586 928 506272948148046584688178834559 929 527510048127255588703226859085 930 549626130609698001326225642469 931 572657091699312642596006450034 932 596640273955010929423672251749 933 621614523903196531211661127664 934 647620251806761432921935552814 935 674699493777911852463558144974 936 702895976325530942062300984292 937 732255183431232541859467526541 938 762824426251870746811885916435 939 794652915549982613368631864625 940 827791836957528283722383691920 941 862294429182290705982355889880 942 898216065270481439445653979936 943 935614337043403881213670710369 944 974549142830529381338330679514 945 1015082778625976732486759074592 946 1057280032800233606202758836606 947 1101208284503948656279816599788 948 1146937605905840983658981078458 949 1194540868412145753421166932039 950 1244093853020630478536865840896 951 1295675364967999343920022942672 952 1349367352835546352455123672616 953 1405255032284142654855356594528 954 1463427014596146674604201027449 955 1523975440208525200171665884573 956 1586996117428471250980566548053 957 1652588666530014794255078814470 958 1720856669437651513826153429955 959 1791907825210774191688889115915 960 1865854111550791730004638209184 961 1942811952561170513696033778016 962 2022902392999347426371253016249 963 2106251279268448093418771659522 964 2192989447406118651994056705773 965 2283252918337445748448486000457 966 2377183100669023666314456660904 967 2474927001311627093754292943739 968 2576637444229794725363289823113 969 2682473297627816539563840703755 970 2792599709893283677702316600177 971 2907188354631394418405874327027 972 3026417685135756333168605983315 973 3150473198654369417559685446572 974 3279547710822967699079763622733 975 3413841640651819546780300182772 976 3553563306466596160109141820388 977 3698929233218891321805647390521 978 3850164471597576904196654959368 979 4007502929388281331777080646061 980 4171187715545052916346303922835 981 4341471497455585767158847255240 982 4518616871899421109822715892303 983 4702896750217155832655489467693 984 4894594758228079120592037709644 985 5094005651453676952137955610106 986 5301435746225287523398274400519 987 5517203367275713323816785694235 988 5741639312437000800425476125448 989 5975087335089736362880849737769 990 6217904645033290163110810401461 991 6470462428471311606551663595416 992 6733146387832664685514189182482 993 7006357302174726739266710382369 994 7290511608943792858545400311477 995 7586042007896064299832047163628 996 7893398088012595091143023867228 997 8213046978272455468283611232141 998 8545474023180496917626247627376 999 8891183483979294799236285182321 1000 9250699266509365240198711047705