0  0 
 1  1 
 2  2 
 3  3 
 4  28 
 5  125 
 6  366 
 7  847 
 8  1688 
 9  3033 
 10  5050 
 11  7931 
 12  11892 
 13  17173 
 14  24038 
 15  32775 
 16  43696 
 17  57137 
 18  73458 
 19  93043 
 20  116300 
 21  143661 
 22  175582 
 23  212543 
 24  255048 
 25  303625 
 26  358826 
 27  421227 
 28  491428 
 29  570053 
 30  657750 
 31  755191 
 32  863072 
 33  982113 
 34  1113058 
 35  1256675 
 36  1413756 
 37  1585117 
 38  1771598 
 39  1974063 
 40  2193400 
 41  2430521 
 42  2686362 
 43  2961883 
 44  3258068 
 45  3575925 
 46  3916486 
 47  4280807 
 48  4669968 
 49  5085073 
 50  5527250 
 51  5997651 
 52  6497452 
 53  7027853 
 54  7590078 
 55  8185375 
 56  8815016 
 57  9480297 
 58  10182538 
 59  10923083 
 60  11703300 
 61  12524581 
 62  13388342 
 63  14296023 
 64  15249088 
 65  16249025 
 66  17297346 
 67  18395587 
 68  19545308 
 69  20748093 
 70  22005550 
 71  23319311 
 72  24691032 
 73  26122393 
 74  27615098 
 75  29170875 
 76  30791476 
 77  32478677 
 78  34234278 
 79  36060103 
 80  37958000 
 81  39929841 
 82  41977522 
 83  44102963 
 84  46308108 
 85  48594925 
 86  50965406 
 87  53421567 
 88  55965448 
 89  58599113 
 90  61324650 
 91  64144171 
 92  67059812 
 93  70073733 
 94  73188118 
 95  76405175 
 96  79727136 
 97  83156257 
 98  86694818 
 99  90345123 
 100  94109500 
 101  97990301 
 102  101989902 
 103  106110703 
 104  110355128 
 105  114725625 
 106  119224666 
 107  123854747 
 108  128618388 
 109  133518133 
 110  138556550 
 111  143736231 
 112  149059792 
 113  154529873 
 114  160149138 
 115  165920275 
 116  171845996 
 117  177929037 
 118  184172158 
 119  190578143 
 120  197149800 
 121  203889961 
 122  210801482 
 123  217887243 
 124  225150148 
 125  232593125 
 126  240219126 
 127  248031127 
 128  256032128 
 129  264225153 
 130  272613250 
 131  281199491 
 132  289986972 
 133  298978813 
 134  308178158 
 135  317588175 
 136  327212056 
 137  337053017 
 138  347114298 
 139  357399163 
 140  367910900 
 141  378652821 
 142  389628262 
 143  400840583 
 144  412293168 
 145  423989425 
 146  435932786 
 147  448126707 
 148  460574668 
 149  473280173 
 150  486246750 
 151  499477951 
 152  512977352 
 153  526748553 
 154  540795178 
 155  555120875 
 156  569729316 
 157  584624197 
 158  599809238 
 159  615288183 
 160  631064800 
 161  647142881 
 162  663526242 
 163  680218723 
 164  697224188 
 165  714546525 
 166  732189646 
 167  750157487 
 168  768454008 
 169  787083193 
 170  806049050 
 171  825355611 
 172  845006932 
 173  865007093 
 174  885360198 
 175  906070375 
 176  927141776 
 177  948578577 
 178  970384978 
 179  992565203 
 180  1015123500 
 181  1038064141 
 182  1061391422 
 183  1085109663 
 184  1109223208 
 185  1133736425 
 186  1158653706 
 187  1183979467 
 188  1209718148 
 189  1235874213 
 190  1262452150 
 191  1289456471 
 192  1316891712 
 193  1344762433 
 194  1373073218 
 195  1401828675 
 196  1431033436 
 197  1460692157 
 198  1490809518 
 199  1521390223 
 200  1552439000 
 201  1583960601 
 202  1615959802 
 203  1648441403 
 204  1681410228 
 205  1714871125 
 206  1748828966 
 207  1783288647 
 208  1818255088 
 209  1853733233 
 210  1889728050 
 211  1926244531 
 212  1963287692 
 213  2000862573 
 214  2038974238 
 215  2077627775 
 216  2116828296 
 217  2156580937 
 218  2196890858 
 219  2237763243 
 220  2279203300 
 221  2321216261 
 222  2363807382 
 223  2406981943 
 224  2450745248 
 225  2495102625 
 226  2540059426 
 227  2585621027 
 228  2631792828 
 229  2678580253 
 230  2725988750 
 231  2774023791 
 232  2822690872 
 233  2871995513 
 234  2921943258 
 235  2972539675 
 236  3023790356 
 237  3075700917 
 238  3128276998 
 239  3181524263 
 240  3235448400 
 241  3290055121 
 242  3345350162 
 243  3401339283 
 244  3458028268 
 245  3515422925 
 246  3573529086 
 247  3632352607 
 248  3691899368 
 249  3752175273 
 250  3813186250 
 251  3874938251 
 252  3937437252 
 253  4000689253 
 254  4064700278 
 255  4129476375 
 256  4195023616 
 257  4261348097 
 258  4328455938 
 259  4396353283 
 260  4465046300 
 261  4534541181 
 262  4604844142 
 263  4675961423 
 264  4747899288 
 265  4820664025 
 266  4894261946 
 267  4968699387 
 268  5043982708 
 269  5120118293 
 270  5197112550 
 271  5274971911 
 272  5353702832 
 273  5433311793 
 274  5513805298 
 275  5595189875 
 276  5677472076 
 277  5760658477 
 278  5844755678 
 279  5929770303 
 280  6015709000 
 281  6102578441 
 282  6190385322 
 283  6279136363 
 284  6368838308 
 285  6459497925 
 286  6551122006 
 287  6643717367 
 288  6737290848 
 289  6831849313 
 290  6927399650 
 291  7023948771 
 292  7121503612 
 293  7220071133 
 294  7319658318 
 295  7420272175 
 296  7521919736 
 297  7624608057 
 298  7728344218 
 299  7833135323 
 300  7938988500 
 301  8045910901 
 302  8153909702 
 303  8262992103 
 304  8373165328 
 305  8484436625 
 306  8596813266 
 307  8710302547 
 308  8824911788 
 309  8940648333 
 310  9057519550 
 311  9175532831 
 312  9294695592 
 313  9415015273 
 314  9536499338 
 315  9659155275 
 316  9782990596 
 317  9908012837 
 318  10034229558 
 319  10161648343 
 320  10290276800 
 321  10420122561 
 322  10551193282 
 323  10683496643 
 324  10817040348 
 325  10951832125 
 326  11087879726 
 327  11225190927 
 328  11363773528 
 329  11503635353 
 330  11644784250 
 331  11787228091 
 332  11930974772 
 333  12076032213 
 334  12222408358 
 335  12370111175 
 336  12519148656 
 337  12669528817 
 338  12821259698 
 339  12974349363 
 340  13128805900 
 341  13284637421 
 342  13441852062 
 343  13600457983 
 344  13760463368 
 345  13921876425 
 346  14084705386 
 347  14248958507 
 348  14414644068 
 349  14581770373 
 350  14750345750 
 351  14920378551 
 352  15091877152 
 353  15264849953 
 354  15439305378 
 355  15615251875 
 356  15792697916 
 357  15971651997 
 358  16152122638 
 359  16334118383 
 360  16517647800 
 361  16702719481 
 362  16889342042 
 363  17077524123 
 364  17267274388 
 365  17458601525 
 366  17651514246 
 367  17846021287 
 368  18042131408 
 369  18239853393 
 370  18439196050 
 371  18640168211 
 372  18842778732 
 373  19047036493 
 374  19252950398 
 375  19460529375 
 376  19669782376 
 377  19880718377 
 378  20093346378 
 379  20307675403 
 380  20523714500 
 381  20741472741 
 382  20960959222 
 383  21182183063 
 384  21405153408 
 385  21629879425 
 386  21856370306 
 387  22084635267 
 388  22314683548 
 389  22546524413 
 390  22780167150 
 391  23015621071 
 392  23252895512 
 393  23491999833 
 394  23732943418 
 395  23975735675 
 396  24220386036 
 397  24466903957 
 398  24715298918 
 399  24965580423 
 400  25217758000 
 401  25471841201 
 402  25727839602 
 403  25985762803 
 404  26245620428 
 405  26507422125 
 406  26771177566 
 407  27036896447 
 408  27304588488 
 409  27574263433 
 410  27845931050 
 411  28119601131 
 412  28395283492 
 413  28672987973 
 414  28952724438 
 415  29234502775 
 416  29518332896 
 417  29804224737 
 418  30092188258 
 419  30382233443 
 420  30674370300 
 421  30968608861 
 422  31264959182 
 423  31563431343 
 424  31864035448 
 425  32166781625 
 426  32471680026 
 427  32778740827 
 428  33087974228 
 429  33399390453 
 430  33712999750 
 431  34028812391 
 432  34346838672 
 433  34667088913 
 434  34989573458 
 435  35314302675 
 436  35641286956 
 437  35970536717 
 438  36302062398 
 439  36635874463 
 440  36971983400 
 441  37310399721 
 442  37651133962 
 443  37994196683 
 444  38339598468 
 445  38687349925 
 446  39037461686 
 447  39389944407 
 448  39744808768 
 449  40102065473 
 450  40461725250 
 451  40823798851 
 452  41188297052 
 453  41555230653 
 454  41924610478 
 455  42296447375 
 456  42670752216 
 457  43047535897 
 458  43426809338 
 459  43808583483 
 460  44192869300 
 461  44579677781 
 462  44969019942 
 463  45360906823 
 464  45755349488 
 465  46152359025 
 466  46551946546 
 467  46954123187 
 468  47358900108 
 469  47766288493 
 470  48176299550 
 471  48588944511 
 472  49004234632 
 473  49422181193 
 474  49842795498 
 475  50266088875 
 476  50692072676 
 477  51120758277 
 478  51552157078 
 479  51986280503 
 480  52423140000 
 481  52862747041 
 482  53305113122 
 483  53750249763 
 484  54198168508 
 485  54648880925 
 486  55102398606 
 487  55558733167 
 488  56017896248 
 489  56479899513 
 490  56944754650 
 491  57412473371 
 492  57883067412 
 493  58356548533 
 494  58832928518 
 495  59312219175 
 496  59794432336 
 497  60279579857 
 498  60767673618 
 499  61258725523 
 500  61752747500 
 501  62249751501 
 502  62749749502 
 503  63252753503 
 504  63758775528 
 505  64267827625 
 506  64779921866 
 507  65295070347 
 508  65813285188 
 509  66334578533 
 510  66858962550 
 511  67386449431 
 512  67917051392 
 513  68450780673 
 514  68987649538 
 515  69527670275 
 516  70070855196 
 517  70617216637 
 518  71166766958 
 519  71719518543 
 520  72275483800 
 521  72834675161 
 522  73397105082 
 523  73962786043 
 524  74531730548 
 525  75103951125 
 526  75679460326 
 527  76258270727 
 528  76840394928 
 529  77425845553 
 530  78014635250 
 531  78606776691 
 532  79202282572 
 533  79801165613 
 534  80403438558 
 535  81009114175 
 536  81618205256 
 537  82230724617 
 538  82846685098 
 539  83466099563 
 540  84088980900 
 541  84715342021 
 542  85345195862 
 543  85978555383 
 544  86615433568 
 545  87255843425 
 546  87899797986 
 547  88547310307 
 548  89198393468 
 549  89853060573 
 550  90511324750 
 551  91173199151 
 552  91838696952 
 553  92507831353 
 554  93180615578 
 555  93857062875 
 556  94537186516 
 557  95220999797 
 558  95908516038 
 559  96599748583 
 560  97294710800 
 561  97993416081 
 562  98695877842 
 563  99402109523 
 564  100112124588 
 565  100825936525 
 566  101543558846 
 567  102265005087 
 568  102990288808 
 569  103719423593 
 570  104452423050 
 571  105189300811 
 572  105930070532 
 573  106674745893 
 574  107423340598 
 575  108175868375 
 576  108932342976 
 577  109692778177 
 578  110457187778 
 579  111225585603 
 580  111997985500 
 581  112774401341 
 582  113554847022 
 583  114339336463 
 584  115127883608 
 585  115920502425 
 586  116717206906 
 587  117518011067 
 588  118322928948 
 589  119131974613 
 590  119945162150 
 591  120762505671 
 592  121584019312 
 593  122409717233 
 594  123239613618 
 595  124073722675 
 596  124912058636 
 597  125754635757 
 598  126601468318 
 599  127452570623 
 600  128307957000 
 601  129167641801 
 602  130031639402 
 603  130899964203 
 604  131772630628 
 605  132649653125 
 606  133531046166 
 607  134416824247 
 608  135307001888 
 609  136201593633 
 610  137100614050 
 611  138004077731 
 612  138911999292 
 613  139824393373 
 614  140741274638 
 615  141662657775 
 616  142588557496 
 617  143518988537 
 618  144453965658 
 619  145393503643 
 620  146337617300 
 621  147286321461 
 622  148239630982 
 623  149197560743 
 624  150160125648 
 625  151127340625 
 626  152099220626 
 627  153075780627 
 628  154057035628 
 629  155043000653 
 630  156033690750 
 631  157029120991 
 632  158029306472 
 633  159034262313 
 634  160044003658 
 635  161058545675 
 636  162077903556 
 637  163102092517 
 638  164131127798 
 639  165165024663 
 640  166203798400 
 641  167247464321 
 642  168296037762 
 643  169349534083 
 644  170407968668 
 645  171471356925 
 646  172539714286 
 647  173613056207 
 648  174691398168 
 649  175774755673 
 650  176863144250 
 651  177956579451 
 652  179055076852 
 653  180158652053 
 654  181267320678 
 655  182381098375 
 656  183500000816 
 657  184624043697 
 658  185753242738 
 659  186887613683 
 660  188027172300 
 661  189171934381 
 662  190321915742 
 663  191477132223 
 664  192637599688 
 665  193803334025 
 666  194974351146 
 667  196150666987 
 668  197332297508 
 669  198519258693 
 670  199711566550 
 671  200909237111 
 672  202112286432 
 673  203320730593 
 674  204534585698 
 675  205753867875 
 676  206978593276 
 677  208208778077 
 678  209444438478 
 679  210685590703 
 680  211932251000 
 681  213184435641 
 682  214442160922 
 683  215705443163 
 684  216974298708 
 685  218248743925 
 686  219528795206 
 687  220814468967 
 688  222105781648 
 689  223402749713 
 690  224705389650 
 691  226013717971 
 692  227327751212 
 693  228647505933 
 694  229972998718 
 695  231304246175 
 696  232641264936 
 697  233984071657 
 698  235332683018 
 699  236687115723 
 700  238047386500 
 701  239413512101 
 702  240785509302 
 703  242163394903 
 704  243547185728 
 705  244936898625 
 706  246332550466 
 707  247734158147 
 708  249141738588 
 709  250555308733 
 710  251974885550 
 711  253400486031 
 712  254832127192 
 713  256269826073 
 714  257713599738 
 715  259163465275 
 716  260619439796 
 717  262081540437 
 718  263549784358 
 719  265024188743 
 720  266504770800 
 721  267991547761 
 722  269484536882 
 723  270983755443 
 724  272489220748 
 725  274000950125 
 726  275518960926 
 727  277043270527 
 728  278573896328 
 729  280110855753 
 730  281654166250 
 731  283203845291 
 732  284759910372 
 733  286322379013 
 734  287891268758 
 735  289466597175 
 736  291048381856 
 737  292636640417 
 738  294231390498 
 739  295832649763 
 740  297440435900 
 741  299054766621 
 742  300675659662 
 743  302303132783 
 744  303937203768 
 745  305577890425 
 746  307225210586 
 747  308879182107 
 748  310539822868 
 749  312207150773 
 750  313881183750 
 751  315561939751 
 752  317249436752 
 753  318943692753 
 754  320644725778 
 755  322352553875 
 756  324067195116 
 757  325788667597 
 758  327516989438 
 759  329252178783 
 760  330994253800 
 761  332743232681 
 762  334499133642 
 763  336261974923 
 764  338031774788 
 765  339808551525 
 766  341592323446 
 767  343383108887 
 768  345180926208 
 769  346985793793 
 770  348797730050 
 771  350616753411 
 772  352442882332 
 773  354276135293 
 774  356116530798 
 775  357964087375 
 776  359818823576 
 777  361680757977 
 778  363549909178 
 779  365426295803 
 780  367309936500 
 781  369200849941 
 782  371099054822 
 783  373004569863 
 784  374917413808 
 785  376837605425 
 786  378765163506 
 787  380700106867 
 788  382642454348 
 789  384592224813 
 790  386549437150 
 791  388514110271 
 792  390486263112 
 793  392465914633 
 794  394453083818 
 795  396447789675 
 796  398450051236 
 797  400459887557 
 798  402477317718 
 799  404502360823 
 800  406535036000 
 801  408575362401 
 802  410623359202 
 803  412679045603 
 804  414742440828 
 805  416813564125 
 806  418892434766 
 807  420979072047 
 808  423073495288 
 809  425175723833 
 810  427285777050 
 811  429403674331 
 812  431529435092 
 813  433663078773 
 814  435804624838 
 815  437954092775 
 816  440111502096 
 817  442276872337 
 818  444450223058 
 819  446631573843 
 820  448820944300 
 821  451018354061 
 822  453223822782 
 823  455437370143 
 824  457659015848 
 825  459888779625 
 826  462126681226 
 827  464372740427 
 828  466626977028 
 829  468889410853 
 830  471160061750 
 831  473438949591 
 832  475726094272 
 833  478021515713 
 834  480325233858 
 835  482637268675 
 836  484957640156 
 837  487286368317 
 838  489623473198 
 839  491968974863 
 840  494322893400 
 841  496685248921 
 842  499056061562 
 843  501435351483 
 844  503823138868 
 845  506219443925 
 846  508624286886 
 847  511037688007 
 848  513459667568 
 849  515890245873 
 850  518329443250 
 851  520777280051 
 852  523233776652 
 853  525698953453 
 854  528172830878 
 855  530655429375 
 856  533146769416 
 857  535646871497 
 858  538155756138 
 859  540673443883 
 860  543199955300 
 861  545735310981 
 862  548279531542 
 863  550832637623 
 864  553394649888 
 865  555965589025 
 866  558545475746 
 867  561134330787 
 868  563732174908 
 869  566339028893 
 870  568954913550 
 871  571579849711 
 872  574213858232 
 873  576856959993 
 874  579509175898 
 875  582170526875 
 876  584841033876 
 877  587520717877 
 878  590209599878 
 879  592907700903 
 880  595615042000 
 881  598331644241 
 882  601057528722 
 883  603792716563 
 884  606537228908 
 885  609291086925 
 886  612054311806 
 887  614826924767 
 888  617608947048 
 889  620400399913 
 890  623201304650 
 891  626011682571 
 892  628831555012 
 893  631660943333 
 894  634499868918 
 895  637348353175 
 896  640206417536 
 897  643074083457 
 898  645951372418 
 899  648838305923 
 900  651734905500 
 901  654641192701 
 902  657557189102 
 903  660482916303 
 904  663418395928 
 905  666363649625 
 906  669318699066 
 907  672283565947 
 908  675258271988 
 909  678242838933 
 910  681237288550 
 911  684241642631 
 912  687255922992 
 913  690280151473 
 914  693314349938 
 915  696358540275 
 916  699412744396 
 917  702476984237 
 918  705551281758 
 919  708635658943 
 920  711730137800 
 921  714834740361 
 922  717949488682 
 923  721074404843 
 924  724209510948 
 925  727354829125 
 926  730510381526 
 927  733676190327 
 928  736852277728 
 929  740038665953 
 930  743235377250 
 931  746442433891 
 932  749659858172 
 933  752887672413 
 934  756125898958 
 935  759374560175 
 936  762633678456 
 937  765903276217 
 938  769183375898 
 939  772473999963 
 940  775775170900 
 941  779086911221 
 942  782409243462 
 943  785742190183 
 944  789085773968 
 945  792440017425 
 946  795804943186 
 947  799180573907 
 948  802566932268 
 949  805964040973 
 950  809371922750 
 951  812790600351 
 952  816220096552 
 953  819660434153 
 954  823111635978 
 955  826573724875 
 956  830046723716 
 957  833530655397 
 958  837025542838 
 959  840531408983 
 960  844048276800 
 961  847576169281 
 962  851115109442 
 963  854665120323 
 964  858226224988 
 965  861798446525 
 966  865381808046 
 967  868976332687 
 968  872582043608 
 969  876198963993 
 970  879827117050 
 971  883466526011 
 972  887117214132 
 973  890779204693 
 974  894452520998 
 975  898137186375 
 976  901833224176 
 977  905540657777 
 978  909259510578 
 979  912989806003 
 980  916731567500 
 981  920484818541 
 982  924249582622 
 983  928025883263 
 984  931813744008 
 985  935613188425 
 986  939424240106 
 987  943246922667 
 988  947081259748 
 989  950927275013 
 990  954784992150 
 991  958654434871 
 992  962535626912 
 993  966428592033 
 994  970333354018 
 995  974249936675 
 996  978178363836 
 997  982118659357 
 998  986070847118 
 999  990034951023 
 1000  994010995000