0  0 
 1  1 
 2  10 
 3  51 
 4  180 
 5  501 
 6  1182 
 7  2471 
 8  4712 
 9  8361 
 10  14002 
 11  22363 
 12  34332 
 13  50973 
 14  73542 
 15  103503 
 16  142544 
 17  192593 
 18  255834 
 19  334723 
 20  432004 
 21  550725 
 22  694254 
 23  866295 
 24  1070904 
 25  1312505 
 26  1595906 
 27  1926315 
 28  2309356 
 29  2751085 
 30  3258006 
 31  3837087 
 32  4495776 
 33  5242017 
 34  6084266 
 35  7031507 
 36  8093268 
 37  9279637 
 38  10601278 
 39  12069447 
 40  13696008 
 41  15493449 
 42  17474898 
 43  19654139 
 44  22045628 
 45  24664509 
 46  27526630 
 47  30648559 
 48  34047600 
 49  37741809 
 50  41750010 
 51  46091811 
 52  50787620 
 53  55858661 
 54  61326990 
 55  67215511 
 56  73547992 
 57  80349081 
 58  87644322 
 59  95460171 
 60  103824012 
 61  112764173 
 62  122309942 
 63  132491583 
 64  143340352 
 65  154888513 
 66  167169354 
 67  180217203 
 68  194067444 
 69  208756533 
 70  224322014 
 71  240802535 
 72  258237864 
 73  276668905 
 74  296137714 
 75  316687515 
 76  338362716 
 77  361208925 
 78  385272966 
 79  410602895 
 80  437248016 
 81  465258897 
 82  494687386 
 83  525586627 
 84  558011076 
 85  592016517 
 86  627660078 
 87  665000247 
 88  704096888 
 89  745011257 
 90  787806018 
 91  832545259 
 92  879294508 
 93  928120749 
 94  979092438 
 95  1032279519 
 96  1087753440 
 97  1145587169 
 98  1205855210 
 99  1268633619 
 100  1334000020 
 101  1402033621 
 102  1472815230 
 103  1546427271 
 104  1622953800 
 105  1702480521 
 106  1785094802 
 107  1870885691 
 108  1959943932 
 109  2052361981 
 110  2148234022 
 111  2247655983 
 112  2350725552 
 113  2457542193 
 114  2568207162 
 115  2682823523 
 116  2801496164 
 117  2924331813 
 118  3051439054 
 119  3182928343 
 120  3318912024 
 121  3459504345 
 122  3604821474 
 123  3754981515 
 124  3910104524 
 125  4070312525 
 126  4235729526 
 127  4406481535 
 128  4582696576 
 129  4764504705 
 130  4952038026 
 131  5145430707 
 132  5344818996 
 133  5550341237 
 134  5762137886 
 135  5980351527 
 136  6205126888 
 137  6436610857 
 138  6674952498 
 139  6920303067 
 140  7172816028 
 141  7432647069 
 142  7699954118 
 143  7974897359 
 144  8257639248 
 145  8548344529 
 146  8847180250 
 147  9154315779 
 148  9469922820 
 149  9794175429 
 150  10127250030 
 151  10469325431 
 152  10820582840 
 153  11181205881 
 154  11551380610 
 155  11931295531 
 156  12321141612 
 157  12721112301 
 158  13131403542 
 159  13552213791 
 160  13983744032 
 161  14426197793 
 162  14879781162 
 163  15344702803 
 164  15821173972 
 165  16309408533 
 166  16809622974 
 167  17322036423 
 168  17846870664 
 169  18384350153 
 170  18934702034 
 171  19498156155 
 172  20074945084 
 173  20665304125 
 174  21269471334 
 175  21887687535 
 176  22520196336 
 177  23167244145 
 178  23829080186 
 179  24505956515 
 180  25198128036 
 181  25905852517 
 182  26629390606 
 183  27369005847 
 184  28124964696 
 185  28897536537 
 186  29686993698 
 187  30493611467 
 188  31317668108 
 189  32159444877 
 190  33019226038 
 191  33897298879 
 192  34793953728 
 193  35709483969 
 194  36644186058 
 195  37598359539 
 196  38572307060 
 197  39566334389 
 198  40580750430 
 199  41615867239 
 200  42672000040 
 201  43749467241 
 202  44848590450 
 203  45969694491 
 204  47113107420 
 205  48279160541 
 206  49468188422 
 207  50680528911 
 208  51916523152 
 209  53176515601 
 210  54460854042 
 211  55769889603 
 212  57103976772 
 213  58463473413 
 214  59848740782 
 215  61260143543 
 216  62698049784 
 217  64162831033 
 218  65654862274 
 219  67174521963 
 220  68722192044 
 221  70298257965 
 222  71903108694 
 223  73537136735 
 224  75200738144 
 225  76894312545 
 226  78618263146 
 227  80372996755 
 228  82158923796 
 229  83976458325 
 230  85826018046 
 231  87708024327 
 232  89622902216 
 233  91571080457 
 234  93552991506 
 235  95569071547 
 236  97619760508 
 237  99705502077 
 238  101826743718 
 239  103983936687 
 240  106177536048 
 241  108408000689 
 242  110675793338 
 243  112981380579 
 244  115325232868 
 245  117707824549 
 246  120129633870 
 247  122591142999 
 248  125092838040 
 249  127635209049 
 250  130218750050 
 251  132843959051 
 252  135511338060 
 253  138221393101 
 254  140974634230 
 255  143771575551 
 256  146612735232 
 257  149498635521 
 258  152429802762 
 259  155406767411 
 260  158430064052 
 261  161500231413 
 262  164617812382 
 263  167783354023 
 264  170997407592 
 265  174260528553 
 266  177573276594 
 267  180936215643 
 268  184349913884 
 269  187814943773 
 270  191331882054 
 271  194901309775 
 272  198523812304 
 273  202199979345 
 274  205930404954 
 275  209715687555 
 276  213556429956 
 277  217453239365 
 278  221406727406 
 279  225417510135 
 280  229486208056 
 281  233613446137 
 282  237799853826 
 283  242046065067 
 284  246352718316 
 285  250720456557 
 286  255149927318 
 287  259641782687 
 288  264196679328 
 289  268815278497 
 290  273498246058 
 291  278246252499 
 292  283059972948 
 293  287940087189 
 294  292887279678 
 295  297902239559 
 296  302985660680 
 297  308138241609 
 298  313360685650 
 299  318653700859 
 300  324018000060 
 301  329454300861 
 302  334963325670 
 303  340545801711 
 304  346202461040 
 305  351934040561 
 306  357741282042 
 307  363624932131 
 308  369585742372 
 309  375624469221 
 310  381741874062 
 311  387938723223 
 312  394215787992 
 313  400573844633 
 314  407013674402 
 315  413536063563 
 316  420141803404 
 317  426831690253 
 318  433606525494 
 319  440467115583 
 320  447414272064 
 321  454448811585 
 322  461571555914 
 323  468783331955 
 324  476084971764 
 325  483477312565 
 326  490961196766 
 327  498537471975 
 328  506206991016 
 329  513970611945 
 330  521829198066 
 331  529783617947 
 332  537834745436 
 333  545983459677 
 334  554230645126 
 335  562577191567 
 336  571023994128 
 337  579571953297 
 338  588221974938 
 339  596974970307 
 340  605831856068 
 341  614793554309 
 342  623860992558 
 343  633035103799 
 344  642316826488 
 345  651707104569 
 346  661206887490 
 347  670817130219 
 348  680538793260 
 349  690372842669 
 350  700320250070 
 351  710381992671 
 352  720559053280 
 353  730852420321 
 354  741263087850 
 355  751792055571 
 356  762440328852 
 357  773208918741 
 358  784098841982 
 359  795111121031 
 360  806246784072 
 361  817506865033 
 362  828892403602 
 363  840404445243 
 364  852044041212 
 365  863812248573 
 366  875710130214 
 367  887738754863 
 368  899899197104 
 369  912192537393 
 370  924619862074 
 371  937182263395 
 372  949880839524 
 373  962716694565 
 374  975690938574 
 375  988804687575 
 376  1002059063576 
 377  1015455194585 
 378  1028994214626 
 379  1042677263755 
 380  1056505488076 
 381  1070480039757 
 382  1084602077046 
 383  1098872764287 
 384  1113293271936 
 385  1127864776577 
 386  1142588460938 
 387  1157465513907 
 388  1172497130548 
 389  1187684512117 
 390  1203028866078 
 391  1218531406119 
 392  1234193352168 
 393  1250015930409 
 394  1266000373298 
 395  1282147919579 
 396  1298459814300 
 397  1314937308829 
 398  1331581660870 
 399  1348394134479 
 400  1365376000080 
 401  1382528534481 
 402  1399853020890 
 403  1417350748931 
 404  1435023014660 
 405  1452871120581 
 406  1470896375662 
 407  1489100095351 
 408  1507483601592 
 409  1526048222841 
 410  1544795294082 
 411  1563726156843 
 412  1582842159212 
 413  1602144655853 
 414  1621635008022 
 415  1641314583583 
 416  1661184757024 
 417  1681246909473 
 418  1701502428714 
 419  1721952709203 
 420  1742599152084 
 421  1763443165205 
 422  1784486163134 
 423  1805729567175 
 424  1827174805384 
 425  1848823312585 
 426  1870676530386 
 427  1892735907195 
 428  1915002898236 
 429  1937478965565 
 430  1960165578086 
 431  1983064211567 
 432  2006176348656 
 433  2029503478897 
 434  2053047098746 
 435  2076808711587 
 436  2100789827748 
 437  2124991964517 
 438  2149416646158 
 439  2174065403927 
 440  2198939776088 
 441  2224041307929 
 442  2249371551778 
 443  2274932067019 
 444  2300724420108 
 445  2326750184589 
 446  2353010941110 
 447  2379508277439 
 448  2406243788480 
 449  2433219076289 
 450  2460435750090 
 451  2487895426291 
 452  2515599728500 
 453  2543550287541 
 454  2571748741470 
 455  2600196735591 
 456  2628895922472 
 457  2657847961961 
 458  2687054521202 
 459  2716517274651 
 460  2746237904092 
 461  2776218098653 
 462  2806459554822 
 463  2836963976463 
 464  2867733074832 
 465  2898768568593 
 466  2930072183834 
 467  2961645654083 
 468  2993490720324 
 469  3025609131013 
 470  3058002642094 
 471  3090673017015 
 472  3123622026744 
 473  3156851449785 
 474  3190363072194 
 475  3224158687595 
 476  3258240097196 
 477  3292609109805 
 478  3327267541846 
 479  3362217217375 
 480  3397459968096 
 481  3432997633377 
 482  3468832060266 
 483  3504965103507 
 484  3541398625556 
 485  3578134496597 
 486  3615174594558 
 487  3652520805127 
 488  3690175021768 
 489  3728139145737 
 490  3766415086098 
 491  3805004759739 
 492  3843910091388 
 493  3883133013629 
 494  3922675466918 
 495  3962539399599 
 496  4002726767920 
 497  4043239536049 
 498  4084079676090 
 499  4125249168099 
 500  4166750000100 
 501  4208584168101 
 502  4250753676110 
 503  4293260536151 
 504  4336106768280 
 505  4379294400601 
 506  4422825469282 
 507  4466702018571 
 508  4510926100812 
 509  4555499776461 
 510  4600425114102 
 511  4645704190463 
 512  4691339090432 
 513  4737331907073 
 514  4783684741642 
 515  4830399703603 
 516  4877478910644 
 517  4924924488693 
 518  4972738571934 
 519  5020923302823 
 520  5069480832104 
 521  5118413318825 
 522  5167722930354 
 523  5217411842395 
 524  5267482239004 
 525  5317936312605 
 526  5368776264006 
 527  5420004302415 
 528  5471622645456 
 529  5523633519185 
 530  5576039158106 
 531  5628841805187 
 532  5682043711876 
 533  5735647138117 
 534  5789654352366 
 535  5844067631607 
 536  5898889261368 
 537  5954121535737 
 538  6009766757378 
 539  6065827237547 
 540  6122305296108 
 541  6179203261549 
 542  6236523470998 
 543  6294268270239 
 544  6352440013728 
 545  6411041064609 
 546  6470073794730 
 547  6529540584659 
 548  6589443823700 
 549  6649785909909 
 550  6710569250110 
 551  6771796259911 
 552  6833469363720 
 553  6895590994761 
 554  6958163595090 
 555  7021189615611 
 556  7084671516092 
 557  7148611765181 
 558  7213012840422 
 559  7277877228271 
 560  7343207424112 
 561  7409005932273 
 562  7475275266042 
 563  7542017947683 
 564  7609236508452 
 565  7676933488613 
 566  7745111437454 
 567  7813772913303 
 568  7882920483544 
 569  7952556724633 
 570  8022684222114 
 571  8093305570635 
 572  8164423373964 
 573  8236040245005 
 574  8308158805814 
 575  8380781687615 
 576  8453911530816 
 577  8527550985025 
 578  8601702709066 
 579  8676369370995 
 580  8751553648116 
 581  8827258226997 
 582  8903485803486 
 583  8980239082727 
 584  9057520779176 
 585  9135333616617 
 586  9213680328178 
 587  9292563656347 
 588  9371986352988 
 589  9451951179357 
 590  9532460906118 
 591  9613518313359 
 592  9695126190608 
 593  9777287336849 
 594  9860004560538 
 595  9943280679619 
 596  10027118521540 
 597  10111520923269 
 598  10196490731310 
 599  10282030801719 
 600  10368144000120 
 601  10454833201721 
 602  10542101291330 
 603  10629951163371 
 604  10718385721900 
 605  10807407880621 
 606  10897020562902 
 607  10987226701791 
 608  11078029240032 
 609  11169431130081 
 610  11261435334122 
 611  11354044824083 
 612  11447262581652 
 613  11541091598293 
 614  11635534875262 
 615  11730595423623 
 616  11826276264264 
 617  11922580427913 
 618  12019510955154 
 619  12117070896443 
 620  12215263312124 
 621  12314091272445 
 622  12413557857574 
 623  12513666157615 
 624  12614419272624 
 625  12715820312625 
 626  12817872397626 
 627  12920578657635 
 628  13023942232676 
 629  13127966272805 
 630  13232653938126 
 631  13338008398807 
 632  13444032835096 
 633  13550730437337 
 634  13658104405986 
 635  13766157951627 
 636  13874894294988 
 637  13984316666957 
 638  14094428308598 
 639  14205232471167 
 640  14316732416128 
 641  14428931415169 
 642  14541832750218 
 643  14655439713459 
 644  14769755607348 
 645  14884783744629 
 646  15000527448350 
 647  15116990051879 
 648  15234174898920 
 649  15352085343529 
 650  15470724750130 
 651  15590096493531 
 652  15710203958940 
 653  15831050541981 
 654  15952639648710 
 655  16074974695631 
 656  16198059109712 
 657  16321896328401 
 658  16446489799642 
 659  16571842981891 
 660  16697959344132 
 661  16824842365893 
 662  16952495537262 
 663  17080922358903 
 664  17210126342072 
 665  17340111008633 
 666  17470879891074 
 667  17602436532523 
 668  17734784486764 
 669  17867927318253 
 670  18001868602134 
 671  18136611924255 
 672  18272160881184 
 673  18408519080225 
 674  18545690139434 
 675  18683677687635 
 676  18822485364436 
 677  18962116820245 
 678  19102575716286 
 679  19243865724615 
 680  19385990528136 
 681  19528953820617 
 682  19672759306706 
 683  19817410701947 
 684  19962911732796 
 685  20109266136637 
 686  20256477661798 
 687  20404550067567 
 688  20553487124208 
 689  20703292612977 
 690  20853970326138 
 691  21005524066979 
 692  21157957649828 
 693  21311274900069 
 694  21465479654158 
 695  21620575759639 
 696  21776567075160 
 697  21933457470489 
 698  22091250826530 
 699  22249951035339 
 700  22409562000140 
 701  22570087635341 
 702  22731531866550 
 703  22893898630591 
 704  23057191875520 
 705  23221415560641 
 706  23386573656522 
 707  23552670145011 
 708  23719709019252 
 709  23887694283701 
 710  24056629954142 
 711  24226520057703 
 712  24397368632872 
 713  24569179729513 
 714  24741957408882 
 715  24915705743643 
 716  25090428817884 
 717  25266130727133 
 718  25442815578374 
 719  25620487490063 
 720  25799150592144 
 721  25978809026065 
 722  26159466944794 
 723  26341128512835 
 724  26523797906244 
 725  26707479312645 
 726  26892176931246 
 727  27077894972855 
 728  27264637659896 
 729  27452409226425 
 730  27641213918146 
 731  27831055992427 
 732  28021939718316 
 733  28213869376557 
 734  28406849259606 
 735  28600883671647 
 736  28795976928608 
 737  28992133358177 
 738  29189357299818 
 739  29387653104787 
 740  29587025136148 
 741  29787477768789 
 742  29989015389438 
 743  30191642396679 
 744  30395363200968 
 745  30600182224649 
 746  30806103901970 
 747  31013132679099 
 748  31221273014140 
 749  31430529377149 
 750  31640906250150 
 751  31852408127151 
 752  32065039514160 
 753  32278804929201 
 754  32493708902330 
 755  32709755975651 
 756  32926950703332 
 757  33145297651621 
 758  33364801398862 
 759  33585466535511 
 760  33807297664152 
 761  34030299399513 
 762  34254476368482 
 763  34479833210123 
 764  34706374575692 
 765  34934105128653 
 766  35163029544694 
 767  35393152511743 
 768  35624478729984 
 769  35857012911873 
 770  36090759782154 
 771  36325724077875 
 772  36561910548404 
 773  36799323955445 
 774  37037969073054 
 775  37277850687655 
 776  37518973598056 
 777  37761342615465 
 778  38004962563506 
 779  38249838278235 
 780  38495974608156 
 781  38743376414237 
 782  38992048569926 
 783  39241995961167 
 784  39493223486416 
 785  39745736056657 
 786  39999538595418 
 787  40254636038787 
 788  40511033335428 
 789  40768735446597 
 790  41027747346158 
 791  41288074020599 
 792  41549720469048 
 793  41812691703289 
 794  42076992747778 
 795  42342628639659 
 796  42609604428780 
 797  42877925177709 
 798  43147595961750 
 799  43418621868959 
 800  43691008000160 
 801  43964759468961 
 802  44239881401770 
 803  44516378937811 
 804  44794257229140 
 805  45073521440661 
 806  45354176750142 
 807  45636228348231 
 808  45919681438472 
 809  46204541237321 
 810  46490812974162 
 811  46778501891323 
 812  47067613244092 
 813  47358152300733 
 814  47650124342502 
 815  47943534663663 
 816  48238388571504 
 817  48534691386353 
 818  48832448441594 
 819  49131665083683 
 820  49432346672164 
 821  49734498579685 
 822  50038126192014 
 823  50343234908055 
 824  50649830139864 
 825  50957917312665 
 826  51267501864866 
 827  51578589248075 
 828  51891184927116 
 829  52205294380045 
 830  52520923098166 
 831  52838076586047 
 832  53156760361536 
 833  53476979955777 
 834  53798740913226 
 835  54122048791667 
 836  54446909162228 
 837  54773327609397 
 838  55101309731038 
 839  55430861138407 
 840  55761987456168 
 841  56094694322409 
 842  56428987388658 
 843  56764872319899 
 844  57102354794588 
 845  57441440504669 
 846  57782135155590 
 847  58124444466319 
 848  58468374169360 
 849  58813930010769 
 850  59161117750170 
 851  59509943160771 
 852  59860412029380 
 853  60212530156421 
 854  60566303355950 
 855  60921737455671 
 856  61278838296952 
 857  61637611734841 
 858  61998063638082 
 859  62360199889131 
 860  62724026384172 
 861  63089549033133 
 862  63456773759702 
 863  63825706501343 
 864  64196353209312 
 865  64568719848673 
 866  64942812398314 
 867  65318636850963 
 868  65696199213204 
 869  66075505505493 
 870  66456561762174 
 871  66839374031495 
 872  67223948375624 
 873  67610290870665 
 874  67998407606674 
 875  68388304687675 
 876  68779988231676 
 877  69173464370685 
 878  69568739250726 
 879  69965819031855 
 880  70364709888176 
 881  70765418007857 
 882  71167949593146 
 883  71572310860387 
 884  71978508040036 
 885  72386547376677 
 886  72796435129038 
 887  73208177570007 
 888  73621780986648 
 889  74037251680217 
 890  74454595966178 
 891  74873820174219 
 892  75294930648268 
 893  75717933746509 
 894  76142835841398 
 895  76569643319679 
 896  76998362582400 
 897  77429000044929 
 898  77861562136970 
 899  78296055302579 
 900  78732486000180 
 901  79170860702581 
 902  79611185896990 
 903  80053468085031 
 904  80497713782760 
 905  80943929520681 
 906  81392121843762 
 907  81842297311451 
 908  82294462497692 
 909  82748623990941 
 910  83204788394182 
 911  83662962324943 
 912  84123152415312 
 913  84585365311953 
 914  85049607676122 
 915  85515886183683 
 916  85984207525124 
 917  86454578405573 
 918  86927005544814 
 919  87401495677303 
 920  87878055552184 
 921  88356691933305 
 922  88837411599234 
 923  89320221343275 
 924  89805127973484 
 925  90292138312685 
 926  90781259198486 
 927  91272497483295 
 928  91765860034336 
 929  92261353733665 
 930  92758985478186 
 931  93258762179667 
 932  93760690764756 
 933  94264778174997 
 934  94771031366846 
 935  95279457311687 
 936  95790062995848 
 937  96302855420617 
 938  96817841602258 
 939  97335028572027 
 940  97854423376188 
 941  98376033076029 
 942  98899864747878 
 943  99425925483119 
 944  99954222388208 
 945  100484762584689 
 946  101017553209210 
 947  101552601413539 
 948  102089914364580 
 949  102629499244389 
 950  103171363250190 
 951  103715513594391 
 952  104261957504600 
 953  104810702223641 
 954  105361755009570 
 955  105915123135691 
 956  106470813890572 
 957  107028834578061 
 958  107589192517302 
 959  108151895042751 
 960  108716949504192 
 961  109284363266753 
 962  109854143710922 
 963  110426298232563 
 964  111000834242932 
 965  111577759168693 
 966  112157080451934 
 967  112738805550183 
 968  113322941936424 
 969  113909497099113 
 970  114498478542194 
 971  115089893785115 
 972  115683750362844 
 973  116280055825885 
 974  116878817740294 
 975  117480043687695 
 976  118083741265296 
 977  118689918085905 
 978  119298581777946 
 979  119909739985475 
 980  120523400368196 
 981  121139570601477 
 982  121758258376366 
 983  122379471399607 
 984  123003217393656 
 985  123629504096697 
 986  124258339262658 
 987  124889730661227 
 988  125523686077868 
 989  126160213313837 
 990  126799320186198 
 991  127441014527839 
 992  128085304187488 
 993  128732197029729 
 994  129381700935018 
 995  130033823799699 
 996  130688573536020 
 997  131345958072149 
 998  132005985352190 
 999  132668663336199 
 1000  133334000000200