1 0 2 0 3 0 4 1 5 0 6 0 7 0 8 1 9 1 10 1 11 1 12 2 13 2 14 3 15 3 16 5 17 5 18 7 19 8 20 11 21 12 22 16 23 18 24 24 25 27 26 34 27 39 28 50 29 57 30 70 31 81 32 100 33 115 34 140 35 161 36 195 37 225 38 269 39 311 40 371 41 427 42 505 43 583 44 688 45 791 46 928 47 1067 48 1248 49 1434 50 1668 51 1914 52 2223 53 2546 54 2945 55 3370 56 3889 57 4443 58 5113 59 5834 60 6698 61 7632 62 8740 63 9946 64 11371 65 12919 66 14735 67 16724 68 19042 69 21581 70 24526 71 27761 72 31499 73 35610 74 40336 75 45543 76 51514 77 58092 78 65606 79 73903 80 83347 81 93775 82 105616 83 118698 84 133517 85 149891 86 168388 87 188838 88 211898 89 237381 90 266051 91 297751 92 333348 93 372691 94 416798 95 465539 96 520095 97 580372 98 647725 99 722129 100 805158 101 896832 102 998992 103 1111771 104 1237284 105 1375774 106 1529723 107 1699526 108 1888067 109 2095937 110 2326475 111 2580547 112 2862055 113 3172131 114 3515342 115 3893233 116 4311104 117 4770964 118 5279023 119 5837867 120 6454745 121 7132958 122 7880956 123 8702934 124 9608786 125 10603699 126 11699272 127 12902010 128 14225429 129 15677557 130 17274243 131 19025353 132 20949442 133 23058586 134 25374474 135 27911869 136 30696188 137 33745294 138 37088964 139 40748903 140 44759902 141 49148157 142 53954453 143 59210307 144 64963470 145 71251798 146 78131144 147 85646939 148 93864567 149 102838255 150 112644538 151 123348239 152 135038802 153 147793422 154 161716779 155 176900637 156 193467402 157 211526040 158 231219551 159 252677188 160 276066072 161 301539076 162 329291457 163 359504037 164 392404685 165 428206837 166 467176556 167 509565454 168 555683947 169 605828368 170 660360627 171 719629408 172 784056658 173 854051882 174 930106803 175 1012702229 176 1102410709 177 1199795998 178 1305524736 179 1420257248 180 1544769241 181 1679833535 182 1826352202 183 1985228955 184 2157512531 185 2344258380 186 2546685166 187 2766025003 188 3003692981 189 3261125977 190 3539966774 191 3841889627 192 4168800564 193 4522649026 194 4905645177 195 5320057238 196 5768447084 197 6253451382 198 6778038160 199 7345270779 200 7958585695 201 8621539146 202 9338108528 203 10112419246 204 10949072284 205 11852850282 206 12829072685 207 13883280536 208 15021621254 209 16250509702 210 17577046627 211 19008654599 212 20553530992 213 22220258530 214 24018296648 215 25957563307 216 28048968724 217 30303967274 218 32735135951 219 35355695861 220 38180138970 221 41223715916 222 44503117190 223 48035925464 224 51841353424 225 55939660445 226 60352952999 227 65104561557 228 70219909865 229 75725850863 230 81651609205 231 88028075771 232 94888829527 233 102269386615 234 110208311229 235 118746417469 236 127927973728 237 137799857717 238 148412863812 239 159820806692 240 172081942057 241 185258018004 242 199415817091 243 214626155762 244 230965558487 245 248515201184 246 267362732664 247 287601161122 248 309330831799 249 332658258799 250 357698274727 251 384572803635 252 413413200166 253 444358964430 254 477560285439 255 513176700887 256 551379863483 257 592352143245 258 636289641608 259 683400738518 260 733909371894 261 788053536027 262 846088853415 263 908287023195 264 974939715612 265 1046356976547 266 1122871471644 267 1204836856512 268 1292632403552 269 1386661341367 270 1487355906556 271 1595175662449 272 1710613009996 273 1834191502378 274 1966471862501 275 2108050301473 276 2259565095617 277 2421694927447 278 2595166072284 279 2780750786608 280 2979275164368 281 3191617590865 282 3418717342476 283 3661573134632 284 3921252530753 285 4198890623385 286 4495700337153 287 4812971273516 288 5152081002329 289 5514494117059 290 5901774609114 291 6315585190805 292 6757700862988 293 7230008557637 294 7734522030584 295 8273381892932 296 8848871954404 297 9463419730313 298 10119614389797 299 10820207818843 300 11568134346098 301 12366512467858 302 13218666529073 303 14128129235399 304 15098665494941 305 16134275842201 306 17239222679529 307 18418034767245 308 19675536104109 309 21016851668213 310 22447439221574 311 23973096486927 312 25599996195194 313 27334694925503 314 29184171731650 315 31155838908781 316 33257584582434 317 35497785677265 318 37885354908258 319 40429756278513 320 43141056928659 321 46029945543918 322 49107789592623 323 52386657040691 324 55879379572432 325 59599578083725 326 63561732520243 327 67781211687861 328 72274350427404 329 77058484319976 330 82152035014383 331 87574550496347 332 93346799434924 333 99490817781244 334 106030013126994 335 112989218454618 336 120394807614970 337 128274757179745 338 136658774237657 339 145578367426046 340 155066988396082 341 165160113194002 342 175895398916875 343 187312776779655 344 199454625601294 345 212365878072097 346 226094212928737 347 240690176069582 348 256207393488180 349 272702709115768 350 290236420773402 351 308872436855459 352 328678537833646 353 349726554097955 354 372092655852099 355 395857554732089 356 421106825182113 357 447931132799649 358 476426590667364 359 506695017657893 360 538844333588142 361 572988851135288 362 609249714056330 363 647755226804603 364 688641340553901 365 732052025017994 366 778139807570276 367 827066192325662 368 879002258147341 369 934129130657345 370 992638645614134 371 1054733880088925 372 1120629888417501 373 1190554299542034 374 1264748133465931 375 1343466472574437 376 1426979367423163 377 1515572590660420 378 1609548641980623 379 1709227594292568 380 1814948208640797 381 1927068883379809 382 2045968891111388 383 2172049442735103 384 2305735059770972 385 2447474766548861 386 2597743612654749 387 2757044008023084 388 2925907411885950 389 3104895827079852 390 3294603673694035 391 3495659460769363 392 3708727864683225 393 3934511598464800 394 4173753717199635 395 4427239707295773 396 4695800043603410 397 4980312523501044 398 5281705102976482 399 5600958503157360 400 5939109355579547 401 6297253111687389 402 6676547530807784 403 7078215926546296 404 7503551034416307 405 7953918632794066 406 8430761831198944 407 8935605107408425 408 9470059061771864 409 10035824916686883 410 10634699787028731 411 11268581693210439 412 11939475403199396 413 12649498015750626 414 13400885435429879 415 14195998588778908 416 15037330600073766 417 15927513709963455 418 16869327226972626 419 17865705225407110 420 18919745355545354 421 20034717405913619 422 21214073063682492 423 22461455435512450 424 23780709859379058 425 25175894488007399 426 26651292264047838 427 28211422681248354 428 29861055046389485 429 31605221545584110 430 33449231929436488 431 35398688025065270 432 37459499995224229 433 39637902451583932 434 41940472454056542 435 44374147397255515 436 46946244933664133 437 49664482822977230 438 52537000981912633 439 55572383506110583 440 58779683070117531 441 62168445353476086 442 65748736037722836 443 69531167892135474 444 73526930640118052 445 77747820986791701 446 82206275654969245 447 86915404666097308 448 91889027877050748 449 97141711857883080 450 102688810294814945 451 108546504843880377 452 114731849802601725 453 121262817357782449 454 128158346969794251 455 135438395475436720 456 143123991674176336 457 151237291794518278 458 159801639821147588 459 168841628885421117 460 178383167927416538 461 188453549628115031 462 199081524060892341 463 210297373846180782 464 222132995512935051 465 234621982626014394 466 247799715651429142 467 261703453882517909 468 276372434683124361 469 291847975122714143 470 308173581559507765 471 325395061986934303 472 343560647015917736 473 362721114035940932 474 382929920762426268 475 404243342427229905 476 426720619173644853 477 450424107613611125 478 475419443481807074 479 501775709030746113 480 529565612496793166 481 558865672952221269 482 589756418290701813 483 622322589317634432 484 656653358133270830 485 692842553420150418 486 730988901289274573 487 771196273919223313 488 813573955135516670 489 858236914770744429 490 905306101472993490 491 954908745391232292 492 1007178680956108779 493 1062256680753653544 494 1120290811292570382 495 1181436801213083800 496 1245858433352843351 497 1313727950748274165 498 1385226488638029697 499 1460544522055866751 500 1539882341768008367 501 1623450547631133720 502 1711470572853237891 503 1804175227700109829 504 1901809276900065732 505 2004630038732845510 506 2112908020870040482 507 2226927580373995244 508 2346987623783614633 509 2473402334091018755 510 2606501941449897355 511 2746633523790916212 512 2894161855150425302 513 3049470287235520665 514 3212961683052468228 515 3385059387443224683 516 3566208254439158596 517 3756875715571142642 518 3957552910190532074 519 4168755861209311811 520 4391026718525749942 521 4624935052785621889 522 4871079223030425286 523 5130087800095590764 524 5402621070671199867 525 5689372603075006780 526 5991070901091102466 527 6308481126082349322 528 6642406915258645214 529 6993692275438029784 530 7363223581802694438 531 7751931660089249200 532 8160793983431420350 533 8590836961368511468 534 9043138354059484688 535 9518829788260488585 536 10019099410037498025 537 10545194649790944777 538 11098425136611792414 539 11680165736537609954 540 12291859753903191919 541 12935022269318301505 542 13611243655775175811 543 14322193245359294899 544 15069623190514677364 545 15855372491253965710 546 16681371234866990504 547 17549645018410600809 548 18462319603297157869 549 19421625771139036088 550 20429904433100740983 551 21489611960771754250 552 22603325793932460630 553 23773750292064560402 554 25003722888294987805 555 26296220511452917066 556 27654366338453256672 557 29081436841505008751 558 30580869196108950108 559 32156269013154560421 560 33811418465070581753 561 35550284768153403831 562 37377029095271051861 563 39296015879885625781 564 41311822590111883514 565 43429249932582341117 566 45653332569648356396 567 47989350308536059210 568 50442839851108789497 569 53019607061728720441 570 55725739847329523335 571 58567621606098271217 572 61551945344696452623 573 64685728419371679039 574 67976328007088905221 575 71431457261040572761 576 75059202263278113178 577 78868039727896876520 578 82866855574570141312 579 87064964325021783939 580 91472129449755434142 581 96098584616883208866 582 100955055978403793163 583 106052785445136644822 584 111403555094235861214 585 117019712659990844678 586 122914198260989587099 587 129100572314004410259 588 135593044797456968696 589 142406505814648285105 590 149556557630060725222 591 157059548128950102077 592 164932605884700619871 593 173193676784423119958 594 181861562409212141659 595 190955960120062323043 596 200497505058631175317 597 210507814014670337699 598 221009531382970976839 599 232026377162800302349 600 243583197237296390421 601 255706015887325557045 602 268422090792919251512 603 281759970478749643244 604 295749554473513012277 605 310422156142107408404 606 325810568478421430152 607 341949132820571964359 608 358873810795634434156 609 376622259459251042818 610 395233909957759346057 611 414750049682430123068 612 435213908265543662496 613 456670747392822976136 614 479167954805633267560 615 502755142473213422218 616 527484249333740578596 617 553409648591139689406 618 580588259993685839549 619 609079667088948254542 620 638946239910359639836 621 670253263098706704194 622 703069069945199321754 623 737465182369377749818 624 773516457352206153105 625 811301239848914572086 626 850901522738115125566 627 892403113844548004254 628 935895810630835807212 629 981473582610028374645 630 1029234762116067363514 631 1079282243500171792883 632 1131723691435138247990 633 1186671758413764285040 634 1244244312171604665173 635 1304564673140650209797 636 1367761862715985107029 637 1433970862464777080464 638 1503332885115405687855 639 1575995657481480622966 640 1652113716218509007592 641 1731848716596238143512 642 1815369755248938901720 643 1902853707118078648880 644 1994485577619054105466 645 2090458870281324253175 646 2190975970968297885871 647 2296248548964992260863 648 2406497976120217351064 649 2521955764374116095057 650 2642864022944369041492 651 2769475935549254175156 652 2902056259034059136948 653 3040881843831355331335 654 3186242177722001896987 655 3338439953385119527080 656 3497791661312010486057 657 3664628208635931323107 658 3839295565569147667431 659 4022155440069310604273 660 4213585982552068914638 661 4413982521349142279158 662 4623758330863989065672 663 4843345433209199120207 664 5073195435423466834056 665 5313780403145585413416 666 5565593773000403921580 667 5829151304676654925290 668 6104992075120934828617 669 6393679515940220733232 670 6695802496619769820663 671 7011976454772149094382 672 7342844576221113229222 673 7689079026271295703280 674 8051382235179734692004 675 8430488239328353335011 676 8827164081342376462320 677 9242211270816024158898 678 9676467309137444048751 679 10130807280251742841711 680 10606145511120499676043 681 11103437303910822642268 682 11623680743959738115803 683 12167918585759298186436 684 12737240221318303353469 685 13332783733378050101403 686 13955738038172603642062 687 14607345120464483316993 688 15288902365907311180220 689 16001764993743087331059 690 16747348595275294345245 691 17527131781427577349698 692 18342658945249723264260 693 19195543143010304223493 694 20087469100191560267364 695 21020196346385388953185 696 21995562485895909662585 697 23015486608439417169505 698 24081972847275986879697 699 25197114089590761560843 700 26363095847029983025008 701 27582200291675274319978 702 28856810465977451347208 703 30189414672440357037322 704 31582611052241236642569 705 33039112359130228319275 706 34561750938513663281964 707 36153483918664723465658 708 37817398624741549365398 709 39556718223210343205378 710 41374807608190730558940 711 43275179538032477314174 712 45261501034544697325462 713 47337600053960578349923 714 49507472443034723653009 715 51775289190197679990709 716 54145403986218534638800 717 56622361105215042091853 718 59210903621599977766914 719 61915981974797526602806 720 64742762898547021565507 721 67696638727708275090439 722 70783237100712457533344 723 74008431071746531025625 724 77378349652247665589694 725 80899388797070479416328 726 84578222856450346598778 727 88421816510509898160160 728 92437437209102205525037 729 96632668135240654049789 730 101015421716712496403345 731 105593953705757351535718 732 110376877853355085403919 733 115373181199774567640941 734 120592240010030558687792 735 126043836377820954253289 736 131738175528862185965413 737 137685903849278594758536 738 143898127672415268136170 739 150386432851989970231770 740 157162905157600860466361 741 164240151522956205177331 742 171631322185701015943661 743 179350133751863735408541 744 187410893226884023024978 745 195828523049124874340850 746 204618587171162169304221 747 213797318227876496886954 748 223381645840237811088735 749 233389226097190516100513 750 243838472268413545149344 751 254748586794028142987864 752 266139594608221131308913 753 278032377846826875587320 754 290448712000362613928067 755 303411303566860986529782 756 316943829270881475564229 757 331070976907702039298393 758 345818487884348291305589 759 361213201521504730818666 760 377283101193660291067815 761 394057362376992802250360 762 411566402688492038526451 763 429841933991736483132720 764 448917016659459014298581 765 468826116074714002483856 766 489605161467943145607967 767 511291607178675772260166 768 533924496446891258234077 769 557544527830270592756944 770 582194124360707918599525 771 607917505544414100657130 772 634760762327987370133909 773 662771935143550880441827 774 692001095165049573222958 775 722500428898289670533841 776 754324326247299612105933 777 787529472189852183506694 778 822174942216042467917650 779 858322301673852272633701 780 896035709187806044074160 781 935382024306640689607740 782 976430919559269281667225 783 1019254997087925430673294 784 1063929910051983327603198 785 1110534488985354335158955 786 1159150873316291719561355 787 1209864648247651391386703 788 1262764987222985981584313 789 1317944800192889849349480 790 1375500887924821611976707 791 1435534102588510841375568 792 1498149514879430180752389 793 1563456587931552031934182 794 1631569358302640602196116 795 1702606624303946836491096 796 1776692141979959390917050 797 1853954829032384288479461 798 1934528977018168858028538 799 2018554472139834722367753 800 2106177024983994723085927 801 2197548409552338250910429 802 2292826711969063319345524 803 2392176589237138263903152 804 2495769538457677878814186 805 2603784176915156852778307 806 2716406533475425558575292 807 2833830351732008234559144 808 2956257405382886511807567 809 3083897826308611549371148 810 3216970445871941490923551 811 3355703149948020198167830 812 3500333248246256639539064 813 3651107858474122357196007 814 3808284305948187341500546 815 3972130539247077765294525 816 4142925562559282299251099 817 4320959885368474979187570 818 4506535990180598832033986 819 4699968818987154868983160 820 4901586279224255190775481 821 5111729769977747769122375 822 5330754729253591247008069 823 5559031203124053321703977 824 5796944437633166764541539 825 6044895494337026883185559 826 6303301890431612574535822 827 6572598264413836055704414 828 6853237068303127518866974 829 7145689287444886923444809 830 7450445189003521567395199 831 7768015100247959759409958 832 8098930217824003533631664 833 8443743449204356837780139 834 8803030287604045845797354 835 9177389721646893701202163 836 9567445181171342630055621 837 9973845520563520771990266 838 10397266041114197540354935 839 10838409553897738084379433 840 11298007484786420146569804 841 11776821023217027446965539 842 12275642316448809303610836 843 12795295711057773284058879 844 13336639043541820439319520 845 13900564981919699691385883 846 14488002420344142724906939 847 15099917928760884316786549 848 15737317259791006744173555 849 16401246915028579402429787 850 17092795773100188271617773 851 17813096781851010736909707 852 18563328717186182767577460 853 19344718011118163135227694 854 20158540651744976288284096 855 21006124157910470672732685 856 21888849631482650787756392 857 22808153890217128745677129 858 23765531684369111908124420 859 24762538000253534220431464 860 25800790454161511835508585 861 26881971780083209901096193 862 28007832414908786493982385 863 29180193184827255671869705 864 30400948096878556675238735 865 31672067239669162252322694 866 32995599797511788873158327 867 34373677182312338238867818 868 35808516287793195530515560 869 37302422870712801543981090 870 38857795064024227987656089 871 40477127026995263688025380 872 42163012737613269844699835 873 43918149932687652449622482 874 45745344201382687785934641 875 47647513238013730140399061 876 49627691260280138915947138 877 51689033599220222242082543 878 53834821467535594010760188 879 56068466913057009861623891 880 58393517964509105254499560 881 60813663976869961650030761 882 63332741184031610747758459 883 65954738466621138984442042 884 68683803343278742065116437 885 71524248193858993766952108 886 74480556723486577728899011 887 77557390676585424605886121 888 80759596810495397257660806 889 84092214138497667995938840 890 87560481452597400368319467 891 91169845136640306979895980 892 94925967280901586135629161 893 98834734109536436309491070 894 102902264732880090186959766 895 107134920236860661688679723 896 111539313122426165922971849 897 116122317108189148180630983 898 120891077310172435398994273 899 125853020812870554171655967 900 131015867646566323186856346 901 136387642186204515420047356 902 141976684987897412215332127 903 147791665079533404939005018 904 153841592722783980545723372 905 160135832664237496009264086 906 166684117894267103243146442 907 173496563932712992559561061 908 180583683661396623895981207 909 187956402724000393660626516 910 195626075514846262186548119 911 203604501778669099364036492 912 211903943844547474143580911 913 220537144517767046837558556 914 229517345654530199360482715 915 238858307445092205733569378 916 248574328432119169223796274 917 258680266291788193122892000 918 269191559406446911330588063 919 280124249258437986402307420 920 291495003676078234757168202 921 303321140963638782796713873 922 315620654948650156067075731 923 328412240980786610504938424 924 341715322918161438977893496 925 355550081137874861839262610 926 369937481609340393828254474 927 384899306070011167027439619 928 400458183344926251599356388 929 416637621852685026226246203 930 433462043342378431492639058 931 450956817907293584212577415 932 469148300323259729073932972 933 488063867760898534905855639 934 507731958923233051010760813 935 528182114661620384858427971 936 549445020125314012588260937 937 571552548501597041287121458 938 594537806405928548833305728 939 618435180983314808591006588 940 643280388784789113694636879 941 669110526484798195065628012 942 695964123508148162716493650 943 723881196637232863034014346 944 752903306673318271620934805 945 783073617227894093868915392 946 814436955723363920927864186 947 847039876684763213176979391 948 880930727407678623961023986 949 916159716090154193561251115 950 952778982520093889994808618 951 990842671412490813314104283 952 1030407008494793768196348705 953 1071530379441767381821566975 954 1114273411765456683843459809 955 1158699059769154133974543597 956 1204872692678815338716326892 957 1252862186068916569665557371 958 1302738016704609473126293323 959 1354573360925854566836851313 960 1408444196704413361200197364 961 1464429409508705437293114868 962 1522610902117094498279321737 963 1583073708524616673803157743 964 1645906112094106603753437300 965 1711199768107472969452019865 966 1779049830879228828795086445 967 1849555085599550988701821397 968 1922818085080936536774186684 969 1998945291588093996346697328 970 2078047223937971424582062205 971 2160238610062823314898829833 972 2245638545236986906770058238 973 2334370656174500124716783773 974 2426563271213001214668877155 975 2522349596806308019505062735 976 2621867900556959461959770018 977 2725261701027492568403564157 978 2832679964578730081108133030 979 2944277309491416631291108690 980 3060214217637703366407978751 981 3180657253977658097940153335 982 3305779294166846288285920746 983 3435759760570364721062218230 984 3570784866990333624828484145 985 3711047872423897230001140381 986 3856749344181215117179935314 987 4008097430703730398058884857 988 4165308144436298053995567489 989 4328605655118375399453471816 990 4498222593873699212215180399 991 4674400368490367113472538329 992 4857389490298453232349860963 993 5047449913065719305772061301 994 5244851384348253767472287980 995 5449873809747308775852531322 996 5662807630541009363732811211 997 5883954215175125615437902305 998 6113626265115714850942824763 999 6352148235583115078947211935 1000 6599856771706683389584873067