0  0 
 1  1 
 2  2 
 3  3 
 4  4 
 5  125 
 6  726 
 7  2527 
 8  6728 
 9  15129 
 10  30250 
 11  55451 
 12  95052 
 13  154453 
 14  240254 
 15  360375 
 16  524176 
 17  742577 
 18  1028178 
 19  1395379 
 20  1860500 
 21  2441901 
 22  3160102 
 23  4037903 
 24  5100504 
 25  6375625 
 26  7893626 
 27  9687627 
 28  11793628 
 29  14250629 
 30  17100750 
 31  20389351 
 32  24165152 
 33  28480353 
 34  33390754 
 35  38955875 
 36  45239076 
 37  52307677 
 38  60233078 
 39  69090879 
 40  78961000 
 41  89927801 
 42  102080202 
 43  115511803 
 44  130321004 
 45  146611125 
 46  164490526 
 47  184072727 
 48  205476528 
 49  228826129 
 50  254251250 
 51  281887251 
 52  311875252 
 53  344362253 
 54  379501254 
 55  417451375 
 56  458377976 
 57  502452777 
 58  549853978 
 59  600766379 
 60  655381500 
 61  713897701 
 62  776520302 
 63  843461703 
 64  914941504 
 65  991186625 
 66  1072431426 
 67  1158917827 
 68  1250895428 
 69  1348621629 
 70  1452361750 
 71  1562389151 
 72  1678985352 
 73  1802440153 
 74  1933051754 
 75  2071126875 
 76  2216980876 
 77  2370937877 
 78  2533330878 
 79  2704501879 
 80  2884802000 
 81  3074591601 
 82  3274240402 
 83  3484127603 
 84  3704642004 
 85  3936182125 
 86  4179156326 
 87  4433982927 
 88  4701090328 
 89  4980917129 
 90  5273912250 
 91  5580535051 
 92  5901255452 
 93  6236554053 
 94  6586922254 
 95  6952862375 
 96  7334887776 
 97  7733522977 
 98  8149303778 
 99  8582777379 
 100  9034502500 
 101  9505049501 
 102  9995000502 
 103  10504949503 
 104  11035502504 
 105  11587277625 
 106  12160905226 
 107  12757028027 
 108  13376301228 
 109  14019392629 
 110  14686982750 
 111  15379764951 
 112  16098445552 
 113  16843743953 
 114  17616392754 
 115  18417137875 
 116  19246738676 
 117  20105968077 
 118  20995612678 
 119  21916472879 
 120  22869363000 
 121  23855111401 
 122  24874560602 
 123  25928567403 
 124  27018003004 
 125  28143753125 
 126  29306718126 
 127  30507813127 
 128  31747968128 
 129  33028128129 
 130  34349253250 
 131  35712318851 
 132  37118315652 
 133  38568249853 
 134  40063143254 
 135  41604033375 
 136  43191973576 
 137  44828033177 
 138  46513297578 
 139  48248868379 
 140  50035863500 
 141  51875417301 
 142  53768680702 
 143  55716821303 
 144  57721023504 
 145  59782488625 
 146  61902435026 
 147  64082098227 
 148  66322731028 
 149  68625603629 
 150  70992003750 
 151  73423236751 
 152  75920625752 
 153  78485511753 
 154  81119253754 
 155  83823228875 
 156  86598832476 
 157  89447478277 
 158  92370598478 
 159  95369643879 
 160  98446084000 
 161  101601407201 
 162  104837120802 
 163  108154751203 
 164  111555844004 
 165  115041964125 
 166  118614695926 
 167  122275643327 
 168  126026429928 
 169  129868699129 
 170  133804114250 
 171  137834358651 
 172  141961135852 
 173  146186169653 
 174  150511204254 
 175  154938004375 
 176  159468355376 
 177  164104063377 
 178  168846955378 
 179  173698879379 
 180  178661704500 
 181  183737321101 
 182  188927640902 
 183  194234597103 
 184  199660144504 
 185  205206259625 
 186  210874940826 
 187  216668208427 
 188  222588104828 
 189  228636694629 
 190  234816064750 
 191  241128324551 
 192  247575605952 
 193  254160063553 
 194  260883874754 
 195  267749239875 
 196  274758382276 
 197  281913548477 
 198  289217008278 
 199  296671054879 
 200  304278005000 
 201  312040199001 
 202  319960001002 
 203  328039799003 
 204  336282005004 
 205  344689055125 
 206  353263409726 
 207  362007553527 
 208  370923995728 
 209  380015270129 
 210  389283935250 
 211  398732574451 
 212  408363796052 
 213  418180233453 
 214  428184545254 
 215  438379415375 
 216  448767553176 
 217  459351693577 
 218  470134597178 
 219  481119050379 
 220  492307865500 
 221  503703880901 
 222  515309961102 
 223  527128996903 
 224  539163905504 
 225  551417630625 
 226  563893142626 
 227  576593438627 
 228  589521542628 
 229  602680505629 
 230  616073405750 
 231  629703348351 
 232  643573466152 
 233  657686919353 
 234  672046895754 
 235  686656610875 
 236  701519308076 
 237  716638258677 
 238  732016762078 
 239  747658145879 
 240  763565766000 
 241  779743006801 
 242  796193281202 
 243  812920030803 
 244  829926726004 
 245  847216866125 
 246  864793979526 
 247  882661623727 
 248  900823385528 
 249  919282881129 
 250  938043756250 
 251  957109686251 
 252  976484376252 
 253  996171561253 
 254  1016175006254 
 255  1036498506375 
 256  1057145886976 
 257  1078121003777 
 258  1099427742978 
 259  1121070021379 
 260  1143051786500 
 261  1165377016701 
 262  1188049721302 
 263  1211073940703 
 264  1234453746504 
 265  1258193241625 
 266  1282296560426 
 267  1306767868827 
 268  1331611364428 
 269  1356831276629 
 270  1382431866750 
 271  1408417428151 
 272  1434792286352 
 273  1461560799153 
 274  1488727356754 
 275  1516296381875 
 276  1544272329876 
 277  1572659688877 
 278  1601462979878 
 279  1630686756879 
 280  1660335607000 
 281  1690414150601 
 282  1720927041402 
 283  1751878966603 
 284  1783274647004 
 285  1815118837125 
 286  1847416325326 
 287  1880171933927 
 288  1913390519328 
 289  1947076972129 
 290  1981236217250 
 291  2015873214051 
 292  2050992956452 
 293  2086600473053 
 294  2122700827254 
 295  2159299117375 
 296  2196400476776 
 297  2234010073977 
 298  2272133112778 
 299  2310774832379 
 300  2349940507500 
 301  2389635448501 
 302  2429865001502 
 303  2470634548503 
 304  2511949507504 
 305  2553815332625 
 306  2596237514226 
 307  2639221579027 
 308  2682773090228 
 309  2726897647629 
 310  2771600887750 
 311  2816888483951 
 312  2862766146552 
 313  2909239622953 
 314  2956314697754 
 315  3003997192875 
 316  3052292967676 
 317  3101207919077 
 318  3150747981678 
 319  3200919127879 
 320  3251727368000 
 321  3303178750401 
 322  3355279361602 
 323  3408035326403 
 324  3461452808004 
 325  3515538008125 
 326  3570297167126 
 327  3625736564127 
 328  3681862517128 
 329  3738681383129 
 330  3796199558250 
 331  3854423477851 
 332  3913359616652 
 333  3973014488853 
 334  4033394648254 
 335  4094506688375 
 336  4156357242576 
 337  4218952984177 
 338  4282300626578 
 339  4346406923379 
 340  4411278668500 
 341  4476922696301 
 342  4543345881702 
 343  4610555140303 
 344  4678557428504 
 345  4747359743625 
 346  4816969124026 
 347  4887392649227 
 348  4958637440028 
 349  5030710658629 
 350  5103619508750 
 351  5177371235751 
 352  5251973126752 
 353  5327432510753 
 354  5403756758754 
 355  5480953283875 
 356  5559029541476 
 357  5637993029277 
 358  5717851287478 
 359  5798611898879 
 360  5880282489000 
 361  5962870726201 
 362  6046384321802 
 363  6130831030203 
 364  6216218649004 
 365  6302555019125 
 366  6389848024926 
 367  6478105594327 
 368  6567335698928 
 369  6657546354129 
 370  6748745619250 
 371  6840941597651 
 372  6934142436852 
 373  7028356328653 
 374  7123591509254 
 375  7219856259375 
 376  7317158904376 
 377  7415507814377 
 378  7514911404378 
 379  7615378134379 
 380  7716916509500 
 381  7819535080101 
 382  7923242441902 
 383  8028047236103 
 384  8133958149504 
 385  8240983914625 
 386  8349133309826 
 387  8458415159427 
 388  8568838333828 
 389  8680411749629 
 390  8793144369750 
 391  8907045203551 
 392  9022123306952 
 393  9138387782553 
 394  9255847779754 
 395  9374512494875 
 396  9494391171276 
 397  9615493099477 
 398  9737827617278 
 399  9861404109879 
 400  9986232010000 
 401  10112320798001 
 402  10239680002002 
 403  10368319198003 
 404  10498248010004 
 405  10629476110125 
 406  10762013218726 
 407  10895869104527 
 408  11031053584728 
 409  11167576525129 
 410  11305447840250 
 411  11444677493451 
 412  11585275497052 
 413  11727251912453 
 414  11870616850254 
 415  12015380470375 
 416  12161552982176 
 417  12309144644577 
 418  12458165766178 
 419  12608626705379 
 420  12760537870500 
 421  12913909719901 
 422  13068752762102 
 423  13225077555903 
 424  13382894710504 
 425  13542214885625 
 426  13703048791626 
 427  13865407189627 
 428  14029300891628 
 429  14194740760629 
 430  14361737710750 
 431  14530302707351 
 432  14700446767152 
 433  14872180958353 
 434  15045516400754 
 435  15220464265875 
 436  15397035777076 
 437  15575242209677 
 438  15755094891078 
 439  15936605200879 
 440  16119784571000 
 441  16304644485801 
 442  16491196482202 
 443  16679452149803 
 444  16869423131004 
 445  17061121121125 
 446  17254557868526 
 447  17449745174727 
 448  17646694894528 
 449  17845418936129 
 450  18045929261250 
 451  18248237885251 
 452  18452356877252 
 453  18658298360253 
 454  18866074511254 
 455  19075697561375 
 456  19287179795976 
 457  19500533554777 
 458  19715771231978 
 459  19932905276379 
 460  20151948191500 
 461  20372912535701 
 462  20595810922302 
 463  20820656019703 
 464  21047460551504 
 465  21276237296625 
 466  21506999089426 
 467  21739758819827 
 468  21974529433428 
 469  22211323931629 
 470  22450155371750 
 471  22691036867151 
 472  22933981587352 
 473  23179002758153 
 474  23426113661754 
 475  23675327636875 
 476  23926658078876 
 477  24180118439877 
 478  24435722228878 
 479  24693483011879 
 480  24953414412000 
 481  25215530109601 
 482  25479843842402 
 483  25746369405603 
 484  26015120652004 
 485  26286111492125 
 486  26559355894326 
 487  26834867884927 
 488  27112661548328 
 489  27392751027129 
 490  27675150522250 
 491  27959874293051 
 492  28246936657452 
 493  28536351992053 
 494  28828134732254 
 495  29122299372375 
 496  29418860465776 
 497  29717832624977 
 498  30019230521778 
 499  30323068887379 
 500  30629362512500 
 501  30938126247501 
 502  31249375002502 
 503  31563123747503 
 504  31879387512504 
 505  32198181387625 
 506  32519520523226 
 507  32843420130027 
 508  33169895479228 
 509  33498961902629 
 510  33830634792750 
 511  34164929602951 
 512  34501861847552 
 513  34841447101953 
 514  35183701002754 
 515  35528639247875 
 516  35876277596676 
 517  36226631870077 
 518  36579717950678 
 519  36935551782879 
 520  37294149373000 
 521  37655526789401 
 522  38019700162602 
 523  38386685685403 
 524  38756499613004 
 525  39129158263125 
 526  39504678016126 
 527  39883075315127 
 528  40264366666128 
 529  40648568638129 
 530  41035697863250 
 531  41425771036851 
 532  41818804917652 
 533  42214816327853 
 534  42613822153254 
 535  43015839343375 
 536  43420884911576 
 537  43828975935177 
 538  44240129555578 
 539  44654362978379 
 540  45071693473500 
 541  45492138375301 
 542  45915715082702 
 543  46342441059303 
 544  46772333833504 
 545  47205410998625 
 546  47641690213026 
 547  48081189200227 
 548  48523925749028 
 549  48969917713629 
 550  49419183013750 
 551  49871739634751 
 552  50327605627752 
 553  50786799109753 
 554  51249338263754 
 555  51715241338875 
 556  52184526650476 
 557  52657212580277 
 558  53133317576478 
 559  53612860153879 
 560  54095858894000 
 561  54582332445201 
 562  55072299522802 
 563  55565778909203 
 564  56062789454004 
 565  56563350074125 
 566  57067479753926 
 567  57575197545327 
 568  58086522567928 
 569  58601474009129 
 570  59120071124250 
 571  59642333236651 
 572  60168279737852 
 573  60697930087653 
 574  61231303814254 
 575  61768420514375 
 576  62309299853376 
 577  62853961565377 
 578  63402425453378 
 579  63954711389379 
 580  64510839314500 
 581  65070829239101 
 582  65634701242902 
 583  66202475475103 
 584  66774172154504 
 585  67349811569625 
 586  67929414078826 
 587  68513000110427 
 588  69100590162828 
 589  69692204804629 
 590  70287864674750 
 591  70887590482551 
 592  71491403007952 
 593  72099323101553 
 594  72711371684754 
 595  73327569749875 
 596  73947938360276 
 597  74572498650477 
 598  75201271826278 
 599  75834279164879 
 600  76471542015000 
 601  77113081797001 
 602  77758920003002 
 603  78409078197003 
 604  79063578015004 
 605  79722441165125 
 606  80385689427726 
 607  81053344655527 
 608  81725428773728 
 609  82401963780129 
 610  83082971745250 
 611  83768474812451 
 612  84458495198052 
 613  85153055191453 
 614  85852177155254 
 615  86555883525375 
 616  87264196811176 
 617  87977139595577 
 618  88694734535178 
 619  89417004360379 
 620  90143971875500 
 621  90875659958901 
 622  91612091563102 
 623  92353289714903 
 624  93099277515504 
 625  93850078140625 
 626  94605714840626 
 627  95366210940627 
 628  96131589840628 
 629  96901875015629 
 630  97677090015750 
 631  98457258466351 
 632  99242404068152 
 633  100032550597353 
 634  100827721905754 
 635  101627941920875 
 636  102433234646076 
 637  103243624160677 
 638  104059134620078 
 639  104879790255879 
 640  105705615376000 
 641  106536634364801 
 642  107372871683202 
 643  108214351868803 
 644  109061099536004 
 645  109913139376125 
 646  110770496157526 
 647  111633194725727 
 648  112501260003528 
 649  113374716991129 
 650  114253590766250 
 651  115137906484251 
 652  116027689378252 
 653  116922964759253 
 654  117823758016254 
 655  118730094616375 
 656  119642000104976 
 657  120559500105777 
 658  121482620320978 
 659  122411386531379 
 660  123345824596500 
 661  124285960454701 
 662  125231820123302 
 663  126183429698703 
 664  127140815356504 
 665  128104003351625 
 666  129073020018426 
 667  130047891770827 
 668  131028645102428 
 669  132015306586629 
 670  133007902876750 
 671  134006460706151 
 672  135011006888352 
 673  136021568317153 
 674  137038171966754 
 675  138060844891875 
 676  139089614227876 
 677  140124507190877 
 678  141165551077878 
 679  142212773266879 
 680  143266201217000 
 681  144325862468601 
 682  145391784643402 
 683  146463995444603 
 684  147542522657004 
 685  148627394147125 
 686  149718637863326 
 687  150816281835927 
 688  151920354177328 
 689  153030883082129 
 690  154147896827250 
 691  155271423772051 
 692  156401492358452 
 693  157538131111053 
 694  158681368637254 
 695  159831233627375 
 696  160987754854776 
 697  162150961175977 
 698  163320881530778 
 699  164497544942379 
 700  165680980517500 
 701  166871217446501 
 702  168068285003502 
 703  169272212546503 
 704  170483029517504 
 705  171700765442625 
 706  172925449932226 
 707  174157112681027 
 708  175395783468228 
 709  176641492157629 
 710  177894268697750 
 711  179154143121951 
 712  180421145548552 
 713  181695306180953 
 714  182976655307754 
 715  184265223302875 
 716  185561040625676 
 717  186864137821077 
 718  188174545519678 
 719  189492294437879 
 720  190817415378000 
 721  192149939228401 
 722  193489896963602 
 723  194837319644403 
 724  196192238418004 
 725  197554684518125 
 726  198924689265126 
 727  200302284066127 
 728  201687500415128 
 729  203080369893129 
 730  204480924168250 
 731  205889194995851 
 732  207305214218652 
 733  208729013766853 
 734  210160625658254 
 735  211600081998375 
 736  213047414980576 
 737  214502656886177 
 738  215965840084578 
 739  217436997033379 
 740  218916160278500 
 741  220403362454301 
 742  221898636283702 
 743  223402014578303 
 744  224913530238504 
 745  226433216253625 
 746  227961105702026 
 747  229497231751227 
 748  231041627658028 
 749  232594326768629 
 750  234155362518750 
 751  235724768433751 
 752  237302578128752 
 753  238888825308753 
 754  240483543768754 
 755  242086767393875 
 756  243698530159476 
 757  245318866131277 
 758  246947809465478 
 759  248585394408879 
 760  250231655299000 
 761  251886626564201 
 762  253550342723802 
 763  255222838388203 
 764  256904148259004 
 765  258594307129125 
 766  260293349882926 
 767  262001311496327 
 768  263718227036928 
 769  265444131664129 
 770  267179060629250 
 771  268923049275651 
 772  270676133038852 
 773  272438347446653 
 774  274209728119254 
 775  275990310769375 
 776  277780131202376 
 777  279579225316377 
 778  281387629102378 
 779  283205378644379 
 780  285032510119500 
 781  286869059798101 
 782  288715064043902 
 783  290570559314103 
 784  292435582159504 
 785  294310169224625 
 786  296194357247826 
 787  298088183061427 
 788  299991683591828 
 789  301904895859629 
 790  303827856979750 
 791  305760604161551 
 792  307703174708952 
 793  309655606020553 
 794  311617935589754 
 795  313590201004875 
 796  315572439949276 
 797  317564690201477 
 798  319566989635278 
 799  321579376219879 
 800  323601888020000 
 801  325634563196001 
 802  327677440004002 
 803  329730556796003 
 804  331793952020004 
 805  333867664220125 
 806  335951732036726 
 807  338046194206527 
 808  340151089562728 
 809  342266457035129 
 810  344392335650250 
 811  346528764531451 
 812  348675782899052 
 813  350833430070453 
 814  353001745460254 
 815  355180768580375 
 816  357370539040176 
 817  359571096546577 
 818  361782480904178 
 819  364004732015379 
 820  366237889880500 
 821  368481994597901 
 822  370737086364102 
 823  373003205473903 
 824  375280392320504 
 825  377568687395625 
 826  379868131289626 
 827  382178764691627 
 828  384500628389628 
 829  386833763270629 
 830  389178210320750 
 831  391534010625351 
 832  393901205369152 
 833  396279835836353 
 834  398669943410754 
 835  401071569575875 
 836  403484755915076 
 837  405909544111677 
 838  408345975949078 
 839  410794093310879 
 840  413253938181000 
 841  415725552643801 
 842  418208978884202 
 843  420704259187803 
 844  423211435941004 
 845  425730551631125 
 846  428261648846526 
 847  430804770276727 
 848  433359958712528 
 849  435927257046129 
 850  438506708271250 
 851  441098355483251 
 852  443702241879252 
 853  446318410758253 
 854  448946905521254 
 855  451587769671375 
 856  454241046813976 
 857  456906780656777 
 858  459585015009978 
 859  462275793786379 
 860  464979161001500 
 861  467695160773701 
 862  470423837324302 
 863  473165234977703 
 864  475919398161504 
 865  478686371406625 
 866  481466199347426 
 867  484258926721827 
 868  487064598371428 
 869  489883259241629 
 870  492714954381750 
 871  495559728945151 
 872  498417628189352 
 873  501288697476153 
 874  504172982271754 
 875  507070528146875 
 876  509981380776876 
 877  512905585941877 
 878  515843189526878 
 879  518794237521879 
 880  521758776022000 
 881  524736851227601 
 882  527728509444402 
 883  530733797083603 
 884  533752760662004 
 885  536785446802125 
 886  539831902232326 
 887  542892173786927 
 888  545966308406328 
 889  549054353137129 
 890  552156355132250 
 891  555272361651051 
 892  558402420059452 
 893  561546577830053 
 894  564704882542254 
 895  567877381882375 
 896  571064123643776 
 897  574265155726977 
 898  577480526139778 
 899  580710282997379 
 900  583954474522500 
 901  587213149045501 
 902  590486355004502 
 903  593774140945503 
 904  597076555522504 
 905  600393647497625 
 906  603725465741226 
 907  607072059232027 
 908  610433477057228 
 909  613809768412629 
 910  617200982602750 
 911  620607169040951 
 912  624028377249552 
 913  627464656859953 
 914  630916057612754 
 915  634382629357875 
 916  637864422054676 
 917  641361485772077 
 918  644873870688678 
 919  648401627092879 
 920  651944805383000 
 921  655503456067401 
 922  659077629764602 
 923  662667377203403 
 924  666272749223004 
 925  669893796773125 
 926  673530570914126 
 927  677183122817127 
 928  680851503764128 
 929  684535765148129 
 930  688235958473250 
 931  691952135354851 
 932  695684347519652 
 933  699432646805853 
 934  703197085163254 
 935  706977714653375 
 936  710774587449576 
 937  714587755837177 
 938  718417272213578 
 939  722263189088379 
 940  726125559083500 
 941  730004434933301 
 942  733899869484702 
 943  737811915697303 
 944  741740626643504 
 945  745686055508625 
 946  749648255591026 
 947  753627280302227 
 948  757623183167028 
 949  761636017823629 
 950  765665838023750 
 951  769712697632751 
 952  773776650629752 
 953  777857751107753 
 954  781956053273754 
 955  786071611448875 
 956  790204480068476 
 957  794354713682277 
 958  798522366954478 
 959  802707494663879 
 960  806910151704000 
 961  811130393083201 
 962  815368273924802 
 963  819623849467203 
 964  823897175064004 
 965  828188306184125 
 966  832497298411926 
 967  836824207447327 
 968  841169089105928 
 969  845531999319129 
 970  849912994134250 
 971  854312129714651 
 972  858729462339852 
 973  863165048405653 
 974  867618944424254 
 975  872091207024375 
 976  876581892951376 
 977  881091059067377 
 978  885618762351378 
 979  890165059899379 
 980  894730008924500 
 981  899313666757101 
 982  903916090844902 
 983  908537338753103 
 984  913177468164504 
 985  917836536879625 
 986  922514602816826 
 987  927211724012427 
 988  931927958620828 
 989  936663364914629 
 990  941418001284750 
 991  946191926240551 
 992  950985198409952 
 993  955797876539553 
 994  960630019494754 
 995  965481686259875 
 996  970352935938276 
 997  975243827752477 
 998  980154421044278 
 999  985084775274879 
 1000  990034950025000