1 0 2 0 3 0 4 0 5 1 6 0 7 1 8 3 9 1 10 3 11 7 12 3 13 8 14 14 15 8 16 17 17 26 18 18 19 33 20 47 21 36 22 61 23 81 24 68 25 106 26 137 27 121 28 181 29 224 30 209 31 296 32 362 33 347 34 478 35 570 36 565 37 750 38 890 39 894 40 1166 41 1360 42 1396 43 1774 44 2062 45 2134 46 2677 47 3076 48 3228 49 3973 50 4555 51 4804 52 5854 53 6657 54 7085 55 8513 56 9664 57 10315 58 12299 59 13877 60 14903 61 17579 62 19805 63 21305 64 24975 65 28008 66 30252 67 35168 68 39385 69 42580 70 49247 71 54954 72 59570 73 68444 74 76278 75 82719 76 94639 77 105166 78 114242 79 130009 80 144297 81 156759 82 177759 83 196825 84 214044 85 241664 86 267278 87 290613 88 327116 89 361060 90 392802 91 440551 92 485736 93 528269 94 590934 95 650418 96 707533 97 789071 98 867599 99 943381 100 1049707 101 1152431 102 1253082 103 1390735 104 1525321 105 1657719 106 1836152 107 2011146 108 2185330 109 2415219 110 2642907 111 2870260 112 3166610 113 3460964 114 3757595 115 4137628 116 4518181 117 4902652 118 5390025 119 5879334 120 6377261 121 6999464 122 7628344 123 8269619 124 9063683 125 9868141 126 10693143 127 11702534 128 12730816 129 13787123 130 15069423 131 16378407 132 17729177 133 19352477 134 21017154 135 22737319 136 24790578 137 26899946 138 29087529 139 31676522 140 34346328 141 37118232 142 40379503 143 43747783 144 47255024 145 51351608 146 55595811 147 60019169 148 65159353 149 70491828 150 76062365 151 82495562 152 89186595 153 96181584 154 104223623 155 112597407 156 121368030 157 131397815 158 141863468 159 152831805 160 165325424 161 178374375 162 192070770 163 207600069 164 223847867 165 240910285 166 260188885 167 280375482 168 301599993 169 325485518 170 350531714 171 376876166 172 406432470 173 437445391 174 470097763 175 506603438 176 544952860 177 585342304 178 630374936 179 677707464 180 727596909 181 783051938 182 841394363 183 902903538 184 971108447 185 1042895843 186 1118626926 187 1202376418 188 1290592321 189 1383671633 190 1486382670 191 1594608741 192 1708857524 193 1834629470 194 1967235883 195 2107240468 196 2261065844 197 2423293637 198 2594637722 199 2782499961 200 2980719888 201 3190097403 202 3419257546 203 3661101083 204 3916632419 205 4195782509 206 4490494139 207 4801901838 208 5141555319 209 5500194923 210 5879234581 211 6291960842 212 6727883471 213 7188610871 214 7689567156 215 8218728931 216 8778087356 217 9385370586 218 10026982363 219 10705201529 220 11440573119 221 12217555025 222 13038951730 223 13928357218 224 14868229393 225 15861794496 226 16936351392 227 18071900106 228 19272390053 229 20569145562 230 21939636916 231 23388427089 232 24951704159 233 26603849213 234 28350421421 235 30232912154 236 32222520121 237 34325690842 238 36590289705 239 38983652867 240 41513599281 241 44234966743 242 47111111056 243 50151123410 244 53418181167 245 56870837072 246 60520076371 247 64438225812 248 68578889815 249 72954869158 250 77649384835 251 82610103767 252 87852438305 253 93471594015 254 99409125892 255 105683023154 256 112402702179 257 119502424441 258 127003778080 259 135031851287 260 143513409392 261 152473679452 262 162056261475 263 172179023303 264 182872147009 265 194299693901 266 206370408512 267 219119587410 268 232735375402 269 247115745799 270 262302808884 271 278511384758 272 295628437927 273 313703234959 274 332981890618 275 353338441555 276 374831510282 277 397741940118 278 421930612384 279 447466120419 280 474669927051 281 503387549024 282 533700404872 283 565975112643 284 600041644195 285 635995254680 286 674255229641 287 714633488560 288 757242834947 289 802561196637 290 850382366646 291 900838276298 292 954475075737 293 1011065635399 294 1070765850303 295 1134197943358 296 1201113986159 297 1271696219488 298 1346655156798 299 1425719023469 300 1509102716879 301 1597615332270 302 1690961707535 303 1789392900894 304 1893832172078 305 2003957752807 306 2120065108658 307 2243205126846 308 2373030427618 309 2509885943016 310 2654970063707 311 2807906550321 312 2969100588996 313 3139915651879 314 3319948461350 315 3509671654194 316 3710639138842 317 3922417552428 318 4145561105623 319 4381837053369 320 4630785009224 321 4893050873400 322 5170647593983 323 5463085272187 324 5771119998081 325 6097040224283 326 6440331423417 327 6801873954590 328 7184273045079 329 7586988141309 330 8011048113077 331 8459413694543 332 8931525823420 333 9428581312556 334 9953949063069 335 10507051972916 336 11089286566127 337 11704480162185 338 12352048891963 339 13033615620248 340 13753533282413 341 14511214686355 342 15308550664521 343 16150484879084 344 17036443380990 345 17968621235765 346 18952638584612 347 19987942700938 348 21077087413438 349 22226453601836 350 23435533718407 351 24707289471686 352 26048971913488 353 27460133358582 354 28944214797087 355 30509446364935 356 32155474427362 357 33886285452779 358 35711228315347 359 37630067805570 360 39647429309042 361 41773921060181 362 44009474522760 363 46359442823464 364 48835871771770 365 51438897647646 366 54174723510473 367 57057014117381 368 60086178008300 369 63269386884609 370 66622151860363 371 70145211170625 372 73846864821698 373 77744703980369 374 81839890073755 375 86142009484302 376 90671023586890 377 95428601167169 378 100425823420250 379 105685322751043 380 111209403972208 381 117010852870087 382 123115343045529 383 129525936195773 384 136257394541573 385 143338819744745 386 150774206308408 387 158580570422414 388 166790913971247 389 175410335079888 390 184458458075163 391 193972682129443 392 203959448112658 393 214441354601933 394 225460800196301 395 237025806880415 396 249162408397690 397 261918640863110 398 275304430685806 399 289349728432331 400 304108975445165 401 319594331719160 402 335840263796373 403 352908436656416 404 370813678905245 405 389595605113979 406 409324082441771 407 430017058631759 408 451720074213439 409 474512247313686 410 498415227560242 411 523481308863180 412 549800107197357 413 577397586054180 414 606333801553057 415 636710210399073 416 668557867382566 417 701945671551121 418 736988508586323 419 773723350403514 420 812229245630743 421 852636226930961 422 894988216572412 423 939375821271433 424 985946242964976 425 1034751462219575 426 1085895334128459 427 1139544425992318 428 1195760144999417 429 1254661426558050 430 1316436777210695 431 1381158509551061 432 1448962823112392 433 1520062968576892 434 1594543970042028 435 1672561669137830 436 1754357335115435 437 1840030668183469 438 1929759969925997 439 2023818107695353 440 2122321834338216 441 2225474992324777 442 2333586210750589 443 2446791894192748 444 2565325057389968 445 2689534655524904 446 2819579862871093 447 2955726850893969 448 3098370192475946 449 3247695256921749 450 3404006046259913 451 3567748566392338 452 3739138461068195 453 3918522706834974 454 4106405464131172 455 4303037149526729 456 4508813722016464 457 4724304899640691 458 4949801195144898 459 5185754179650003 460 5432807661756082 461 5691298138776542 462 5961740507036401 463 6244862082246022 464 6541052275626906 465 6850897839304182 466 7175220422244759 467 7514470034282577 468 7869315173090565 469 8240683788676708 470 8629095487966032 471 9035311473415445 472 9460379723211843 473 9904899442178608 474 10369737202428322 475 10856076207975802 476 11364606920633055 477 11896315339915670 478 12452537290027862 479 13034067470455875 480 13642027506759566 481 14277925126523772 482 14942674340681045 483 15637550406320408 484 16364254981164373 485 17123838194319248 486 17917749627387114 487 18747909314935973 488 19615522952502150 489 20522237474679040 490 21470219166807475 491 22460851000470572 492 23496003665408659 493 24578120664787671 494 25708787288726745 495 26890127393358990 496 28124896948446176 497 29414911543345139 498 30762581846520877 499 32171015488056278 500 33642290541000182 501 35179141997677725 502 36785073691677240 503 38462462167181903 504 40214409566466832 505 42044865491005001 506 43956546243538986 507 45952968894919662 508 48038585062102729 509 50216496999044406 510 52490691151977352 511 54866183779902388 512 57346515959460932 513 59936204288475235 514 62640900643208492 515 65464644101473860 516 68412550552857470 517 71490986555604106 518 74704556778908501 519 78059053614792433 520 81561647795571535 521 85217585258083235 522 89033422594553932 523 93017234445036213 524 97174994278088010 525 101514120852473591 526 106043705470374299 527 110770545735605322 528 115703033683346498 529 120851402977964966 530 126223385280201453 531 131828470050733677 532 137678175270712960 533 143781289767940822 534 150148541042705539 535 156792889686681404 536 163724321545732481 537 170954959300239202 538 178499384730992364 539 186368937337154125 540 194577312734817947 541 203140913065148578 542 212072609143693631 543 221387868186993947 544 231105137172899955 545 241239017211428168 546 251806971581163727 547 262829742490978026 548 274323886716003999 549 286309114468380949 550 298808745136980128 551 311841543547585114 552 325429749979277943 553 339599575527726806 554 354372278554846072 555 369772945844970654 556 385831034057354782 557 402570614750349418 558 420019977973802059 559 438212220704701186 560 457174588836644731 561 476938974381830786 562 497542558386700365 563 519016165374790351 564 541395738380449978 565 564723037550542590 566 589032922268450325 567 614365888379556742 568 640768831172322689 569 668281155525582534 570 696948474746781877 571 726823439528496185 572 757950575854401230 573 790381245352462972 574 824174550308855988 575 859380781900210789 576 896057759342658182 577 934271813044173709 578 974079724679521969 579 1015546563341390486 580 1058746758525356653 581 1103744393770451666 582 1150612678066463571 583 1199435111353002814 584 1250283991834114858 585 1303241662388107802 586 1358401782147479989 587 1415845884782350881 588 1475666562780190596 589 1537968848528754250 590 1602844658541647629 591 1670398080683574604 592 1740746880498819904 593 1813994640065787694 594 1890258339901999958 595 1969669994870923008 596 2052346293150904422 597 2138418667658535972 598 2228035079805516877 599 2321326933788806712 600 2418441863100926435 601 2519545667586012511 602 2624786273969049563 603 2734329467239257115 604 2848361002218272903 605 2967047346379920643 606 3090574621307509305 607 3219150895588259998 608 3352963440350249549 609 3492221151585897056 610 3637157049007633691 611 3787981734591488790 612 3944929607363108798 613 4108261576693833296 614 4278214406883416203 615 4455051043282526967 616 4639063568647627661 617 4830518070604553992 618 5029709444984351238 619 5236964605742943478 620 5452582502905622427 621 5676893778329875627 622 5910264262447402064 623 6153029717148120025 624 6405560773315071444 625 6668266727357286274 626 6941524571847085863 627 7225749656012758979 628 7521399820725477420 629 7828898218583972495 630 8148710200878156219 631 8481347806985328566 632 8827285861052641731 633 9187045603818078618 634 9561199581381265803 635 9950280435359465135 636 10354871869701474186 637 10775613958405155310 638 11213104027994422580 639 11667995567995106957 640 12141004009915763937 641 12632799020116342486 642 13144112045192851523 643 13675742586167256748 644 14228441197614720120 645 14803026382141106640 646 15400391420678291907 647 16021377280916367627 648 16666899670079241624 649 17337956450553217471 650 18035489633477746817 651 18760523427244613196 652 19514172309375262255 653 20297491174495915255 654 21111625325303462771 655 21957819236290845161 656 22837253892194518121 657 23751209702711557592 658 24701076040695271126 659 25688174684711087391 660 26713936764529561071 661 27779913117068624707 662 28887582706489568920 663 30038544749576893097 664 31234529985735631155 665 32477192807477359439 666 33768319859399585178 667 35109842274755679350 668 36503610200596040709 669 37951619215131431820 670 39456023643193633843 671 41018891998950525784 672 42642452732698601946 673 44329108688845371316 674 46081171930615369279 675 47901130389067677161 676 49791663594656493012 677 51755355163224049744 678 53794982111167219314 679 55913531937561149727 680 58113890980522042125 681 60399158236864458998 682 62772663947788957966 683 65237631822364741675 684 67797519419693824284 685 70456038331180930869 686 73216788183869158133 687 76083625732542965811 688 79060686817295138574 689 82151989815980190788 690 85361835846126681198 691 88694832610056095024 692 92155464865461094938 693 95748528244142277213 694 99479155193541482145 695 103352349755371011814 696 107373457798227467532 697 111548195190858629597 698 115882144059437249229 699 120381262359172705004 700 125051914523539673914 701 129900326050989976193 702 134933135673860943534 703 140157428646521552383 704 145580146370616345872 705 151208684572294957948 706 157050929515013530976 707 163114619006063300132 708 169407990375815276145 709 175939819811228698795 710 182718730918531415978 711 189753896479916626959 712 197055081242243306086 713 204631893791217320073 714 212494546500415294330 715 220653902010841695591 716 229120663973463095897 717 237906199821280486109 718 247022591331504660893 719 256481759313042174810 720 266296354336881708480 721 276479811663941898604 722 287045404719878486714 723 298007209174927988108 724 309380162696523018378 725 321179041504193383611 726 333419503769211891091 727 346118154531697527251 728 359291439352501349384 729 372956773305811669244 730 387132611599035740137 731 401837253709824985352 732 417090064909596045852 733 432911552993640815411 734 449322075967074623189 735 466343163395009611687 736 483997599874376602826 737 502308028613558665212 738 521298380667880148687 739 540993965641510055006 740 561419963124798271475 741 582602968295831279853 742 604571090593615998856 743 627352324155156328281 744 650976219139229898265 745 675473988955864059173 746 700876750398985906912 747 727217330545821924015 748 754530383413091230776 749 782850489541719355212 750 812214109329572797127 751 842659709814758558653 752 874225712946771705758 753 906952606795284266356 754 940883083483248781612 755 976059824305779291053 756 1012527781409742564449 757 1050334327714752747537 758 1089526866431027204634 759 1130155296491915630188 760 1172272175664987559026 761 1215930140794725717626 762 1261184571591411434313 763 1308093767934676108163 764 1356716166455090653475 765 1407113218089546736494 766 1459349580991163554668 767 1513490117665057751343 768 1569603003215549866179 769 1627759935060740683794 770 1688032894008353716613 771 1750497501065798131796 772 1815233245623046407958 773 1882319992258353532903 774 1951841605719522397754 775 2023886199007032464036 776 2098542366734301184940 777 2175903098995936767385 778 2256066051309485768087 779 2339129483534385658192 780 2425196485334725594975 781 2514375269690063444957 782 2606774795255542504977 783 2702509327422199678768 784 2801698757703176159093 785 2904463885341804399311 786 3010931340255621180287 787 3121233930340315534087 788 3235505556830597780539 789 3353886526928152486136 790 3476523931740564204596 791 3603566167534175380655 792 3735168668463011839690 793 3871494317580449773632 794 4012707544613782732671 795 4158980510979036072964 796 4310493557068027716201 797 4467428844479452807841 798 4629977028503381206547 799 4798337744592464482724 800 4972712761236349183086 801 5153313177162084335553 802 5340359950765697801577 803 5534076526748005516500 804 5734696598713495286065 805 5942464685031890060234 806 6157628190331540557778 807 6380445776583407864753 808 6611187989846748809337 809 6850128714223378654621 810 7097554198450542238609 811 7353763737668074117947 812 7619060475100762471135 813 7893761133983945203919 814 8178196759607701326018 815 8472702820020646121324 816 8777629697622582992183 817 9093343496417864902901 818 9420215390337867771471 819 9758632932093830537567 820 10109000931842576637414 821 10471729997205849031323 822 10847248722143238278604 823 11236004642908201406163 824 11638451910734208599685 825 12055064427277647870364 826 12486336885188066270889 827 12932771509294480417813 828 13394892211086081324488 829 13873245720899889890957 830 14368387329861011484409 831 14880896140273699926363 832 15411376298076034855227 833 15960441661952195959342 834 16528732233284110602701 835 17116915497214812547896 836 17725669941232762506210 837 18355702753450149762227 838 19007751282492885071926 839 19682565321230309507569 840 20380926169907814772073 841 21103648224796864553538 842 21851559938010835142604 843 22625524347957671204404 844 23426440808823557533601 845 24255224529894577381885 846 25112828684682728045541 847 26000246293069155188266 848 26918488238118067671021 849 27868607072117738138680 850 28851699065652797776915 851 29868880591365155063017 852 30921313755327774129053 853 32010208627121597356851 854 33136797873766985162784 855 34302364352834148052675 856 35508243540392889320827 857 36755796288665138552113 858 38046438528926599064874 859 39381643914078492317235 860 40762914566432638104642 861 42191813047712692655429 862 43669965236191721247638 863 45199028920060461872582 864 46780728205174477861724 865 48416856646683528190294 866 50109243535262690736632 867 51859790923969019326718 868 53670477037946848278718 869 55543320088388339420869 870 57480418115131840694469 871 59483952698142939497918 872 61556150124728579860085 873 63699324256915392591275 874 65915880572599457083262 875 68208274497488516346883 876 70579057523776287255439 877 73030881609142889514181 878 75566454474228754636145 879 78188589213475225091429 880 80900209084968820587118 881 83704299558358145638879 882 86603961678736573149633 883 89602417280834527473000 884 92702957560114810604731 885 95909000467174274546293 886 99224096385314267968766 887 102651872979584349261302 888 106196096922077652906440 889 109860680072702040933580 890 113649620347063397745213 891 117567068092220907140494 892 121617332816834773927763 893 125804819798484298497325 894 130134101455656561739828 895 134609924674592541438784 896 139237142860831775400729 897 144020792675385197208294 898 148966102012913374548973 899 154078417179375954356880 900 159363285390333536696785 901 164826463456678789671924 902 170473839752292865778332 903 176311522898038978545143 904 182345851219690650377767 905 188583309143646278454960 906 195030622524504421085016 907 201694768941967345897355 908 208582888142239366346995 909 215702384496655295555681 910 223060938214051114166025 911 230666409416327568016233 912 238526948254889080685662 913 246651007117781826460333 914 255047237904720240041012 915 263724610362240494350618 916 272692425376118524430874 917 281960204978324709625197 918 291537819506756072438604 919 301435502077083549349372 920 311663730827814429951379 921 322233365549871581209941 922 333155663444973632232158 923 344442153078025856868346 924 356104781173268304260071 925 368155929770942359234146 926 380608281326461665860982 927 393474976415308252537839 928 406769632414719986758267 929 420506199147522474498716 930 434699128296837357791663 931 449363393745409700311355 932 464514337128306349614331 933 480167849810925828812031 934 496340395035925155186150 935 513048842702271368636100 936 530310664827433006503765 937 548143959659250657551727 938 566567274960778775050227 939 585599817937984047022036 940 605261481493993034017867 941 625572655246702775511009 942 646554450980437210010514 943 668228731229207995991665 944 690617907211132551200519 945 713745180932174667914563 946 737634576308347605975870 947 762310723142128350868643 948 787799117094678098509765 949 814126153568316907120377 950 841318896801724737203312 951 869405359007332820540908 952 898414537262429075359834 953 928376166733979846820317 954 959321020378909564700454 955 991280949106246569156769 956 1024288618087919407345270 957 1058377828512156730610238 958 1093583561310474040384164 959 1129941695436950896864023 960 1167489353280614208464963 961 1206264948268306731757884 962 1246307883933707408004705 963 1287658924701133125905015 964 1330360247711812397156086 965 1374455121421315844415833 966 1419988303599564726159961 967 1467006097749105851995331 968 1515556009900866995151746 969 1565687175797903098214951 970 1617450422316698803536928 971 1670897901038887086633377 972 1726083546737765288862366 973 1783063144239320649275093 974 1841893937270481668199943 975 1902635120508779121425353 976 1965347912369170871035834 977 2030095137526423824096957 978 2096941754961724625483641 979 2165954937192553228672814 980 2237203624780533231554204 981 2310759092971533780700951 982 2386695037943347947385902 983 2465087101495585365124722 984 2546013479078351544909241 985 2629555013670242185933396 986 2715794688750458537996271 987 2804818280698492771010890 988 2896714460981958669633802 989 2991574255383371936936728 990 3089491743980583391162170 991 3190564172369581716959720 992 3294891375010844714169133 993 3402576526215903050301909 994 3513726261208376764116245 995 3628450061312823032974893 996 3746861059633083651517046 997 3869076172809807290346652 998 3995215445654965781032644 999 4125402915455824252731968 1000 4259766755378335565256847