# How many ways can you make the sum of a number?

From wikipedia: https://en.wikipedia.org/wiki/Partition_(number_theory)#

>In number theory and combinatorics, a partition of a positive integer *n*, also called an *integer partition*, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. If order matters, the sum becomes a composition. For example, 4 can be partitioned in five distinct ways:
```
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
```

## Examples

### Basic

```python
exp_sum(1) # 1
exp_sum(2) # 2  -> 1+1 , 2
exp_sum(3) # 3 -> 1+1+1, 1+2, 3
exp_sum(4) # 5 -> 1+1+1+1, 1+1+2, 1+3, 2+2, 4
exp_sum(5) # 7 -> 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 5, 2+3

exp_sum(10) # 42
```

### Explosive

```python
exp_sum(50) # 204226
exp_sum(80) # 15796476
exp_sum(100) # 190569292
```

See [here](http://www.numericana.com/data/partition.htm) for more examples.

Difficulty: interview

Starter code:

def exp_sum(n):
	

Solutions:
ANSWERS = {
    0: 1,
    1: 1,
    2: 2,
    3: 3,
    4: 5,
    5: 7,
    6: 11,
    7: 15,
    8: 22,
    9: 30,
    10: 42,
    11: 56,
    12: 77,
    13: 101,
    14: 135,
    15: 176,
    16: 231,
    17: 297,
    18: 385,
    19: 490,
    20: 627,
    21: 792,
    22: 1002,
    23: 1255,
    24: 1575,
    25: 1958,
    26: 2436,
    27: 3010,
    28: 3718,
    29: 4565,
    30: 5604,
    31: 6842,
    32: 8349,
    33: 10143,
    34: 12310,
    35: 14883,
    36: 17977,
    37: 21637,
    38: 26015,
    39: 31185,
    40: 37338,
    41: 44583,
    42: 53174,
    43: 63261,
    44: 75175,
    45: 89134,
    46: 105558,
    47: 124754,
    48: 147273,
    49: 173525,
    50: 204226,
    51: 239943,
    52: 281589,
    53: 329931,
    54: 386155,
    55: 451276,
    56: 526823,
    57: 614154,
    58: 715220,
    59: 831820,
    60: 966467,
    61: 1121505,
    62: 1300156,
    63: 1505499,
    64: 1741630,
    65: 2012558,
    66: 2323520,
    67: 2679689,
    68: 3087735,
    69: 3554345,
    70: 4087968,
    71: 4697205,
    72: 5392783,
    73: 6185689,
    74: 7089500,
    75: 8118264,
    76: 9289091,
    77: 10619863,
    78: 12132164,
    79: 13848650,
    80: 15796476,
    81: 18004327,
    82: 20506255,
    83: 23338469,
    84: 26543660,
    85: 30167357,
    86: 34262962,
    87: 38887673,
    88: 44108109,
    89: 49995925,
    90: 56634173,
    91: 64112359,
    92: 72533807,
    93: 82010177,
    94: 92669720,
    95: 104651419,
    96: 118114304,
    97: 133230930,
    98: 150198136,
    99: 169229875,
    100: 190569292,
    101: 214481126,
    102: 241265379,
    103: 271248950,
    104: 304801365,
    105: 342325709,
    106: 384276336,
    107: 431149389,
    108: 483502844,
    109: 541946240,
    110: 607163746,
    111: 679903203,
    112: 761002156,
    113: 851376628,
    114: 952050665,
    115: 1064144451,
    116: 1188908248,
    117: 1327710076,
    118: 1482074143,
    119: 1653668665,
    120: 1844349560,
    121: 2056148051,
    122: 2291320912,
    123: 2552338241,
    124: 2841940500,
    125: 3163127352,
    126: 3519222692,
    127: 3913864295,
    128: 4351078600,
    129: 4835271870,
    130: 5371315400,
    131: 5964539504,
    132: 6620830889,
    133: 7346629512,
    134: 8149040695,
    135: 9035836076,
    136: 10015581680,
    137: 11097645016,
    138: 12292341831,
    139: 13610949895,
    140: 15065878135,
    141: 16670689208,
    142: 18440293320,
    143: 20390982757,
    144: 22540654445,
    145: 24908858009,
    146: 27517052599,
    147: 30388671978,
    148: 33549419497,
    149: 37027355200,
    150: 40853235313,
    151: 45060624582,
    152: 49686288421,
    153: 54770336324,
    154: 60356673280,
    155: 66493182097,
    156: 73232243759,
    157: 80630964769,
    158: 88751778802,
    159: 97662728555,
    160: 107438159466,
    161: 118159068427,
    162: 129913904637,
    163: 142798995930,
    164: 156919475295,
    165: 172389800255,
    166: 189334822579,
    167: 207890420102,
    168: 228204732751,
    169: 250438925115,
    170: 274768617130,
    171: 301384802048,
    172: 330495499613,
    173: 362326859895,
    174: 397125074750,
    175: 435157697830,
    176: 476715857290,
    177: 522115831195,
    178: 571701605655,
    179: 625846753120,
    180: 684957390936,
    181: 749474411781,
    182: 819876908323,
    183: 896684817527,
    184: 980462880430,
    185: 1071823774337,
    186: 1171432692373,
    187: 1280011042268,
    188: 1398341745571,
    189: 1527273599625,
    190: 1667727404093,
    191: 1820701100652,
    192: 1987276856363,
    193: 2168627105469,
    194: 2366022741845,
    195: 2580840212973,
    196: 2814570987591,
    197: 3068829878530,
    198: 3345365983698,
    199: 3646072432125,
    200: 3972999029388,
    201: 4328363658647,
    202: 4714566886083,
    203: 5134205287973,
    204: 5590088317495,
    205: 6085253859260,
    206: 6622987708040,
    207: 7206841706490,
    208: 7840656226137,
    209: 8528581302375,
    210: 9275102575355,
    211: 10085065885767,
    212: 10963707205259,
    213: 11916681236278,
    214: 12950095925895,
    215: 14070545699287,
    216: 15285151248481,
    217: 16601598107914,
    218: 18028182516671,
    219: 19573856161145,
    220: 21248279009367,
    221: 23061871173849,
    222: 25025873760111,
    223: 27152408925615,
    224: 29454549941750,
    225: 31946390696157,
    226: 34643126322519,
    227: 37561133582570,
    228: 40718063627362,
    229: 44132934884255,
    230: 47826239745920,
    231: 51820051838712,
    232: 56138148670947,
    233: 60806135438329,
    234: 65851585970275,
    235: 71304185514919,
    236: 77195892663512,
    237: 83561103925871,
    238: 90436839668817,
    239: 97862933703585,
    240: 105882246722733,
    241: 114540884553038,
    242: 123888443077259,
    243: 133978259344888,
    244: 144867692496445,
    245: 156618412527946,
    246: 169296722391554,
    247: 182973889854026,
    248: 197726516681672,
    249: 213636919820625,
    250: 230793554364681,
    251: 249291451168559,
    252: 269232701252579,
    253: 290726957916112,
    254: 313891991306665,
    255: 338854264248680,
    256: 365749566870782,
    257: 394723676655357,
    258: 425933084409356,
    259: 459545750448675,
    260: 495741934760846,
    261: 534715062908609,
    262: 576672674947168,
    263: 621837416509615,
    264: 670448123060170,
    265: 722760953690372,
    266: 779050629562167,
    267: 839611730366814,
    268: 904760108316360,
    269: 974834369944625,
    270: 1050197489931117,
    271: 1131238503938606,
    272: 1218374349844333,
    273: 1312051800816215,
    274: 1412749565173450,
    275: 1520980492851175,
    276: 1637293969337171,
    277: 1762278433057269,
    278: 1896564103591584,
    279: 2040825852575075,
    280: 2195786311682516,
    281: 2362219145337711,
    282: 2540952590045698,
    283: 2732873183547535,
    284: 2938929793929555,
    285: 3160137867148997,
    286: 3397584011986773,
    287: 3652430836071053,
    288: 3925922161489422,
    289: 4219388528587095,
    290: 4534253126900886,
    291: 4872038056472084,
    292: 5234371069753672,
    293: 5622992691950605,
    294: 6039763882095515,
    295: 6486674127079088,
    296: 6965850144195831,
    297: 7479565078510584,
    298: 8030248384943040,
    299: 8620496275465025,
    300: 9253082936723602,
    301: 9930972392403501,
    302: 10657331232548839,
    303: 11435542077822104,
    304: 12269218019229465,
    305: 13162217895057704,
    306: 14118662665280005,
    307: 15142952738857194,
    308: 16239786535829663,
    309: 17414180133147295,
    310: 18671488299600364,
    311: 20017426762576945,
    312: 21458096037352891,
    313: 23000006655487337,
    314: 24650106150830490,
    315: 26415807633566326,
    316: 28305020340996003,
    317: 30326181989842964,
    318: 32488293351466654,
    319: 34800954869440830,
    320: 37274405776748077,
    321: 39919565526999991,
    322: 42748078035954696,
    323: 45772358543578028,
    324: 49005643635237875,
    325: 52462044228828641,
    326: 56156602112874289,
    327: 60105349839666544,
    328: 64325374609114550,
    329: 68834885946073850,
    330: 73653287861850339,
    331: 78801255302666615,
    332: 84300815636225119,
    333: 90175434980549623,
    334: 96450110192202760,
    335: 103151466321735325,
    336: 110307860425292772,
    337: 117949491546113972,
    338: 126108517833796355,
    339: 134819180623301520,
    340: 144117936527873832,
    341: 154043597379576030,
    342: 164637479165761044,
    343: 175943559810422753,
    344: 188008647052292980,
    345: 200882556287683159,
    346: 214618299743286299,
    347: 229272286871217150,
    348: 244904537455382406,
    349: 261578907351144125,
    350: 279363328483702152,
    351: 298330063062758076,
    352: 318555973788329084,
    353: 340122810048577428,
    354: 363117512048110005,
    355: 387632532919029223,
    356: 413766180933342362,
    357: 441622981929358437,
    358: 471314064268398780,
    359: 502957566506000020,
    360: 536679070310691121,
    361: 572612058898037559,
    362: 610898403751884101,
    363: 651688879997206959,
    364: 695143713458946040,
    365: 741433159884081684,
    366: 790738119649411319,
    367: 843250788562528427,
    368: 899175348396088349,
    369: 958728697912338045,
    370: 1022141228367345362,
    371: 1089657644424399782,
    372: 1161537834849962850,
    373: 1238057794119125085,
    374: 1319510599727473500,
    375: 1406207446561484054,
    376: 1498478743590581081,
    377: 1596675274490756791,
    378: 1701169427975813525,
    379: 1812356499739472950,
    380: 1930656072350465812,
    381: 2056513475336633805,
    382: 2190401332423765131,
    383: 2332821198543892336,
    384: 2484305294265418180,
    385: 2645418340688763701,
    386: 2816759503217942792,
    387: 2998964447736452194,
    388: 3192707518433532826,
    389: 3398704041358160275,
    390: 3617712763867604423,
    391: 3850538434667429186,
    392: 4098034535626594791,
    393: 4361106170762284114,
    394: 4640713124699623515,
    395: 4937873096788191655,
    396: 5253665124416975163,
    397: 5589233202595404488,
    398: 5945790114707874597,
    399: 6324621482504294325,
    400: 6727090051741041926,
    401: 7154640222653942321,
    402: 7608802843339879269,
    403: 8091200276484465581,
    404: 8603551759348655060,
    405: 9147679068859117602,
    406: 9725512513742021729,
    407: 10339097267123947241,
    408: 10990600063775926994,
    409: 11682316277192317780,
    410: 12416677403151190382,
    411: 13196258966925435702,
    412: 14023788883518847344,
    413: 14902156290309948968,
    414: 15834420884488187770,
    415: 16823822787139235544,
    416: 17873792969689876004,
    417: 18987964267331664557,
    418: 20170183018805933659,
    419: 21424521360255636320,
    420: 22755290216580025259,
    421: 24167053021441363961,
    422: 25664640213837714846,
    423: 27253164546230421739,
    424: 28938037257084798150,
    425: 30724985147095051099,
    426: 32620068617410232189,
    427: 34629700713903575934,
    428: 36760667241831527309,
    429: 39020148000237259665,
    430: 41415739207102358378,
    431: 43955477170518116534,
    432: 46647863284229267991,
    433: 49501890409405150715,
    434: 52527070729108240605,
    435: 55733465144636286656,
    436: 59131714309169618645,
    437: 62733071376043079215,
    438: 66549436566966297367,
    439: 70593393646562135510,
    440: 74878248419470886233,
    441: 79418069346443402240,
    442: 84227730407729499781,
    443: 89322956321353645667,
    444: 94720370257893471820,
    445: 100437544171752847604,
    446: 106493051905239118581,
    447: 112906525199196103354,
    448: 119698712782720205954,
    449: 126891542690981418000,
    450: 134508188001572923840,
    451: 142573136155347404229,
    452: 151112262071917313678,
    453: 160152905244553715585,
    454: 169723951046458040965,
    455: 179855916453958267598,
    456: 190581040442651931034,
    457: 201933379285114688629,
    458: 213948907032733069132,
    459: 226665621435831345565,
    460: 240123655613925192081,
    461: 254365395758574199975,
    462: 269435605212954994471,
    463: 285381555241961986287,
    464: 302253162872576636605,
    465: 320103136152993290544,
    466: 338987127249525432549,
    467: 358963893768162876613,
    468: 380095468763120598477,
    469: 402447339861711475160,
    470: 426088638015652413417,
    471: 451092336355096099864,
    472: 477535459708164115593,
    473: 505499305314204629558,
    474: 535069675351607262125,
    475: 566337121865805599675,
    476: 599397204782301852926,
    477: 634350763653787028583,
    478: 671304203896731807232,
    479: 710369798236628238005,
    480: 751666004194993125591,
    481: 795317798414758232180,
    482: 841457028742823649455,
    483: 890222784951928088294,
    484: 941761789114997698055,
    485: 996228806608573411012,
    486: 1053787078862455346513,
    487: 1114608778936426484248,
    488: 1178875491155735802646,
    489: 1246778716001272919665,
    490: 1318520401612270233223,
    491: 1394313503224447816939,
    492: 1474382572040363953132,
    493: 1558964374994977806173,
    494: 1648308547066172438760,
    495: 1742678277747760981187,
    496: 1842351033503159891466,
    497: 1947619317987658064007,
    498: 2058791472042884901563,
    499: 2176192515439287461625,
    500: 2300165032574323995027,
    501: 2431070104309287327876,
    502: 2569288288377098289281,
    503: 2715220650772245313220,
    504: 2869289850802400662045,
    505: 3031941282464413132742,
    506: 3203644275096202070012,
    507: 3384893356244349844341,
    508: 3576209579998154653671,
    509: 3778141924035171537110,
    510: 3991268758958164118300,
    511: 4216199393504640098482,
    512: 4453575699570940947378,
    513: 4704073821002175842062,
    514: 4968405970488126319775,
    515: 5247322318923878793976,
    516: 5541612982013113936133,
    517: 5852110108921301661040,
    518: 6179690078238084808000,
    519: 6525275806549652788115,
    520: 6889839175409542385648,
    521: 7274403582551733377346,
    522: 7680046623716094332553,
    523: 8107902911527474124146,
    524: 8559167038437716736150,
    525: 9035096690829005915201,
    526: 9537015921990240021538,
    527: 10066318591787500106586,
    528: 10624471981512075020731,
    529: 11213020592521695111580,
    530: 11833590138006300416410,
    531: 12487891737367521803652,
    532: 13177726323474524612308,
    533: 13904989273245567335012,
    534: 14671675272840783232475,
    535: 15479883428970761068959,
    536: 16331822638729701493803,
    537: 17229817230617210720599,
    538: 18176312890390861435034,
    539: 19173882885687454484110,
    540: 20225234604409151266221,
    541: 21333216422211708570598,
    542: 22500824915577356165493,
    543: 23731212437346370138355,
    544: 25027695072821279146420,
    545: 26393760995005382968154,
    546: 27833079238879849385687,
    547: 29349508915133986374841,
    548: 30947108885217475101876,
    549: 32630147920163234060900,
    550: 34403115367205050943160,
    551: 36270732348871285128752,
    552: 38237963520943177237554,
    553: 40310029416409244587122,
    554: 42492419404397720872600,
    555: 44790905293907018009131,
    556: 47211555614160398040338,
    557: 49760750604354432757376,
    558: 52445197947746313627407,
    559: 55271949286085137715955,
    560: 58248417552751868050007,
    561: 61382395164161775318496,
    562: 64682073111542943380454,
    563: 68156060996536236172174,
    564: 71813408056839596203570,
    565: 75663625229609055443637,
    566: 79716708303343130521599,
    567: 83983162210640880002321,
    568: 88474026517495817981253,
    569: 93200902166643654187580,
    570: 98175979536033971312388,
    571: 103412067875563710992446,
    572: 108922626189067392956037,
    573: 114721795630860408658491,
    574: 120824433490320564237125,
    575: 127246148840551966562301,
    576: 134003339931725153597473,
    577: 141113233412529912746558,
    578: 148593925468119890197615,
    579: 156464424966082817448060,
    580: 164744698707340387584240,
    581: 173455718882380096095248,
    582: 182619512839056823919887,
    583: 192259215272078129526277,
    584: 202399122950629095580175,
    585: 213064752104884207160129,
    586: 224282898599046831034631,
    587: 236081701023305130945921,
    588: 248490706844586261413858,
    589: 261540941761240642265710,
    590: 275264982414934173206642,
    591: 289697032618827122974972,
    592: 304873003269975366031783,
    593: 320830596120295386610807,
    594: 337609391590065169560935,
    595: 355250940815002702558187,
    596: 373798862128436852709430,
    597: 393298942187883251157044,
    598: 413799241966727832978027,
    599: 435350207840317348270000,
    600: 458004788008144308553622,
    601: 481818554503286362923739,
    602: 506849831053734861481872,
    603: 533159827070679866278987,
    604: 560812778053476538349420,
    605: 589876092712502332463864,
    606: 620420507127059714307352,
    607: 652520246268116112057164,
    608: 686253193233019826880477,
    609: 721701066553229757379480,
    610: 758949605954969709105721,
    611: 798088766967999186006767,
    612: 839212924798226411060795,
    613: 882421087896683264554175,
    614: 927817121679723721849795,
    615: 975509982873756796925504,
    616: 1025613964982134990453294,
    617: 1078248955392080004474789,
    618: 1133540704665979618906662,
    619: 1191621108583631746910145,
    620: 1252628503530795506440909,
    621: 1316707975853817969920561,
    622: 1384011685831426958558879,
    623: 1454699206941558115141676,
    624: 1528937881135168275063375,
    625: 1606903190858354689128371,
    626: 1688779148601189609516729,
    627: 1774758704783877366657989,
    628: 1865044174831202682776536,
    629: 1959847686321528964669495,
    630: 2059391647140527228529479,
    631: 2163909235608484556362424,
    632: 2273644913597837330081136,
    633: 2388854963699932382735982,
    634: 2509808051552031608082535,
    635: 2636785814481962651219075,
    636: 2770083477684418110395121,
    637: 2910010499193691843303014,
    638: 3056891244979232231862474,
    639: 3211065695545980277248740,
    640: 3372890185488482409685019,
    641: 3542738177508596708707874,
    642: 3721001072479541451508397,
    643: 3908089057205582486668934,
    644: 4104431991606013700457110,
    645: 4310480337124871462076948,
    646: 4526706128254173781044298,
    647: 4753603989138067267826945,
    648: 4991692197319220372390544,
    649: 5241513796775816319683700,
    650: 5503637762499727151307095,
    651: 5778660218961559003723580,
    652: 6067205714919484306343541,
    653: 6369928557132709817142929,
    654: 6687514205661440172553650,
    655: 7020680733548749464953877,
    656: 7370180353811425547662139,
    657: 7736801016790889035132284,
    658: 8121368081058512888507057,
    659: 8524746061205131302394950,
    660: 8947840456000332817673697,
    661: 9391599660555044587641517,
    662: 9857016966290401433259592,
    663: 10345132652677367520056676,
    664: 10857036174895938656583295,
    665: 11393868451739000294452939,
    666: 11956824258286445517629485,
    667: 12547154728067493595502055,
    668: 13166169969647255482980383,
    669: 13815241802783448943206160,
    670: 14495806619536377005379418,
    671: 15209368375944215483241988,
    672: 15957501720133631304230773,
    673: 16741855262985451980947171,
    674: 17564154997755650263621500,
    675: 18426207875324210441995136,
    676: 19329905542049511423199336,
    677: 20277228247502764885900784,
    678: 21270248929688765106878025,
    679: 22311137485682880566295780,
    680: 23402165235974892374954302,
    681: 24545709591163085124246501,
    682: 25744258930034131533263392,
    683: 27000417698448800353553865,
    684: 28316911738879831363625420,
    685: 29696593860867277871605321,
    686: 31142449663120060247020395,
    687: 32657603618448918933404658,
    688: 34245325433219728719773420,
    689: 35909036693513349075724695,
    690: 37652317810725762600765183,
    691: 39478915279883795756623331,
    692: 41392749264546866860893416,
    693: 43397921522754943172592795,
    694: 45498723689129703063649450,
    695: 47699645928878027716139269,
    696: 50005385980149860746062163,
    697: 52420858601901549459658530,
    698: 54951205445179608281719072,
    699: 57601805366500810491219000,
    700: 60378285202834474611028659,
    701: 63286531028521032840985510,
    702: 66332699915362724119980694,
    703: 69523232218023552371152320,
    704: 72864864407855341219969825,
    705: 76364642479247406973532354,
    706: 80029935953661656574123574,
    707: 83868452507581852374822598,
    708: 87888253251761884175130183,
    709: 92097768690318501305952845,
    710: 96505815389469697877049934,
    711: 101121613386982294887579670,
    712: 105954804374756131323439197,
    713: 111015470688345108146850290,
    714: 116314155138696524440183805,
    715: 121861881722882938654960142,
    716: 127670177252209281782740521,
    717: 133751093937700984130081285,
    718: 140117232974725477106760252,
    719: 146781769170263852819573505,
    720: 153758476658245881594406593,
    721: 161061755750279477635534762,
    722: 168706660971164630122439117,
    723: 176708930330666271859881567,
    724: 185085015885255746880625875,
    725: 193852115645795752984189381,
    726: 203028206889569986197651315,
    727: 212632080937520072186590492,
    728: 222683379460186024851577401,
    729: 233202632378520643600875145,
    730: 244211297428606706709925517,
    731: 255731801462210865865001525,
    732: 267787583558210323920375877,
    733: 280403140023083872114273884,
    734: 293604071362025285843562670,
    735: 307417131305664218954016427,
    736: 321870277981032622582593573,
    737: 336992727319136467572139095,
    738: 352815008795455957133215652,
    739: 369369023603738655757458075,
    740: 386688105367749941220651375,
    741: 404807083500032850651734059,
    742: 423762349321394151918928481,
    743: 443591925059596733749014862,
    744: 464335535850798483634138280,
    745: 486034684872448271784326296,
    746: 508732731741838107613602755,
    747: 532474974320122372524707631,
    748: 557308734067567635805394638,
    749: 583283445101886813536239875,
    750: 610450747117966916191771809,
    751: 638864582333908382360557376,
    752: 668581296635294279311393900,
    753: 699659745096778286894322787,
    754: 732161402067670820574405230,
    755: 766150476015982127183457373,
    756: 801694029333610862568750951,
    757: 838862103313805798709299373,
    758: 877727848520950325159242658,
    759: 918367660781873199488134935,
    760: 960861323037560814483873080,
    761: 1005292153304074193879898920,
    762: 1051747159001957690209588887,
    763: 1100317197924192833923669753,
    764: 1151097146124113726578727360,
    765: 1204186073016375022219516992,
    766: 1259687423996378387111229150,
    767: 1317709210896221493178043552,
    768: 1378364210608578997366598385,
    769: 1441770172223648126550509165,
    770: 1508050033038752490738311726,
    771: 1577332143815074048889599022,
    772: 1649750503671651735806603894,
    773: 1725445005022910006140645612,
    774: 1804561688982956164492944650,
    775: 1887253011677361609828822380,
    776: 1973678121921532286407950000,
    777: 2064003150743712843868729636,
    778: 2158401513250589964731360493,
    779: 2257054223353982965849642005,
    780: 2360150221898687182164777966,
    781: 2467886718753771981901721670,
    782: 2580469549453004933593920862,
    783: 2698113546994164480174756373,
    784: 2821042929432312216467202070,
    785: 2949491703928193388274450292,
    786: 3083704087940340693022764503,
    787: 3223934948277725160271634798,
    788: 3370450258759473520427114109,
    789: 3523527577258789108163787100,
    790: 3683456542940343404363084600,
    791: 3850539394533563994343413787,
    792: 4025091510519029370421431033,
    793: 4207441972141088280734057870,
    794: 4397934150197476827913759850,
    795: 4596926316595586652827474186,
    796: 4804792281705797515062559743,
    797: 5021922058584382849328869242,
    798: 5248722555182613689484387822,
    799: 5485618295704258477069984050,
    800: 5733052172321422504456911979,
    801: 5991486228508002426815719537,
    802: 6261402475301701333080509487,
    803: 6543303741858946450905285538,
    804: 6837714561722963378455094385,
    805: 7145182096283051986707103605,
    806: 7466277096963606051213804496,
    807: 7801594907743960700949000443,
    808: 8151756509675604512522473567,
    809: 8517409609130970421571757565,
    810: 8899229771588828461969917962,
    811: 9297921602834531195851268718,
    812: 9714219979529959777862768265,
    813: 10148891331187245215547993864,
    814: 10602734975663191221223594155,
    815: 11076584510377034355391142064,
    816: 11571309261543787320061392679,
    817: 12087815793808125625662163707,
    818: 12627049482760689878061744701,
    819: 13189996152918959195978870030,
    820: 13777683783859651786576215682,
    821: 14391184287298069419105856949,
    822: 15031615358023124634594092724,
    823: 15700142401714084441377203063,
    824: 16397980542787591098996821750,
    825: 17126396715550358417594267021,
    826: 17886711842065410771034749979,
    827: 18680303100276877491522988120,
    828: 19508606286081561360311437674,
    829: 20373118273183778133458320225,
    830: 21275399574724765449983360003,
    831: 22217077010838260632179411313,
    832: 23199846486451169343993151122,
    833: 24225475883821531494697782922,
    834: 25295808074486832813101046425,
    835: 26412764055483014097178757689,
    836: 27578346214889968804237171486,
    837: 28794641731961759722351371983,
    838: 30063826117310982372086476080,
    839: 31388166898835484452139885750,
    840: 32770027459303858556350798600,
    841: 34211871031752548278772284453,
    842: 35716264859093977687647313415,
    843: 37285884524590579748861394570,
    844: 38923518460115987806848673270,
    845: 40632072639400673752129300324,
    846: 42414575463747094337180792099,
    847: 44274182847997609942310578598,
    848: 46214183514849300594196193732,
    849: 48238004505931946889525421000,
    850: 50349216918401212177548479675,
    851: 52551541876147039010384562987,
    852: 54848856745079917639394818823,
    853: 57245201602333536237114022805,
    854: 59744785969613964515539259105,
    855: 62351995821331449988466091712,
    856: 65071400878573831543609957267,
    857: 67907762200418949875852866531,
    858: 70866040084540107092698343096,
    859: 73951402289532005957331751320,
    860: 77169232591877674590168543277,
    861: 80525139690988018278755885205,
    862: 84024966476277979232856334449,
    863: 87674799670795146675673859587,
    864: 91480979866491345649258758095,
    865: 95450111966823518214883921610,
    866: 99589076052990565170686659417,
    867: 103905038690755971019484297576,
    868: 108405464695475636367939373595,
    869: 113098129373644577851404473535,
    870: 117991131259998859170817958839,
    871: 123092905369958432777075796052,
    872: 128412236987976529870072690275,
    873: 133958276013169939669531019316,
    874: 139740551884446204479331411000,
    875: 145768989108216487062234772851,
    876: 152053923412691097170490155923,
    877: 158606118553696417431847045996,
    878: 165436783797931931934295220337,
    879: 172557592110602218633091543840,
    880: 179980699075416049556058362840,
    881: 187718762576041099642814429720,
    882: 195784963269243383580949581161,
    883: 204193025881123335512830178821,
    884: 212957241359090878236182734445,
    885: 222092489913497780851227603386,
    886: 231614264984172822820073009257,
    887: 241538698168481624527315178361,
    888: 251882585148964518765460484674,
    889: 262663412660090356154504995095,
    890: 273899386535208029575034561337,
    891: 285609460876378579895067651923,
    892: 297813368391435715163322531331,
    893: 310531651944349233813920512829,
    894: 323785697366761254448562966675,
    895: 337597767580427105501057917306,
    896: 351991038082228660789452118410,
    897: 366989633845435601723754690835,
    898: 382618667692977386826261193199,
    899: 398904280200653395819254517900,
    900: 415873681190459054784114365430,
    901: 433555192876539531087229255477,
    902: 451978294728708525214023001725,
    903: 471173670120985588372050797999,
    904: 491173254835220446432862090800,
    905: 512010287492584845146484412308,
    906: 533719361988531136324395159455,
    907: 556336482009740068071399064008,
    908: 579899117714618242279047917300,
    909: 604446264662056374189988834755,
    910: 630018505076433611630379753807,
    911: 656658071540248718776792346785,
    912: 684408913209287275550344075013,
    913: 713316764648893234122621625751,
    914: 743429217393715213042975617565,
    915: 774795794337240928934816284899,
    916: 807468027061529837515792402675,
    917: 841499536221802614337232047468,
    918: 876946115104959930393838357571,
    919: 913865816485680423486405066750,
    920: 952319042908502961911588247808,
    921: 992368640529229737341624411924,
    922: 1034079996654109332431762911842,
    923: 1077521141120571341397403386532,
    924: 1122762851668802145076610697775,
    925: 1169878763459173895733432737528,
    926: 1218945482896482311379736998403,
    927: 1270042705928112564209840426896,
    928: 1323253340989653981276400185806,
    929: 1378663636778122744608506419570,
    930: 1436363315039845896899358328033,
    931: 1496445708567209282036578487803,
    932: 1559007904605896258842021462474,
    933: 1624150893881942976244820893255,
    934: 1691979725465930503404211099660,
    935: 1762603667699924360130192603237,
    936: 1836136375421380008668856717532,
    937: 1912696063727159213943851080855,
    938: 1992405688530070149968413761596,
    939: 2075393134169954709485716047155,
    940: 2161791408351324312330912522447,
    941: 2251738844689892053427982289844,
    942: 2345379313161090374436414551558,
    943: 2442862438754801545567295092897,
    944: 2544343828652090726779455860435,
    945: 2649985308251720770267133439311,
    946: 2759955166386673475403099789409,
    947: 2874428410083806869907819978392,
    948: 2993587029233173241168779714732,
    949: 3117620271547411926979127053250,
    950: 3246724928206047105940972859506,
    951: 3381105630594468612010288127863,
    952: 3520975158562887897616477410546,
    953: 3666554760646647127956344306190,
    954: 3818074486705953843294627812035,
    955: 3975773533460423034845675035419,
    956: 4139900603411771887815710365915,
    957: 4310714277666637214536144927329,
    958: 4488483403190813123215639907302,
    959: 4673487495046245204241629451110,
    960: 4866017154182911354694265206413,
    961: 5066374501379277964399166419563,
    962: 5274873627947390097986152243705,
    963: 5491841063841846500452896053582,
    964: 5717616263835974099255567733750,
    965: 5952552112453464578853008309794,
    966: 6197015448369619941842104648894,
    967: 6451387609023188709970129910797,
    968: 6716064996207615136996693074302,
    969: 6991459663439386169435859778910,
    970: 7277999925931103886207676505429,
    971: 7576130994027952290703815097177,
    972: 7886315630998429231248733036419,
    973: 8209034836103596418058528755338,
    974: 8544788553903729460741526714750,
    975: 8894096410797147287955714755082,
    976: 9257498479823236816318777820416,
    977: 9635556074800288403768986034253,
    978: 10028852574908795418824727341746,
    979: 10437994280872373856676062879735,
    980: 10863611303931504965592652844878,
    981: 11306358488849924787366667765407,
    982: 11766916372239763961801564990016,
    983: 12245992177539511607834487453052,
    984: 12744320848028628464246059627690,
    985: 13262666119314202551196742822008,
    986: 13801821632778520931079437719552,
    987: 14362612091531863067120268402228,
    988: 14945894460472306341153073892017,
    989: 15552559212113915719970799358900,
    990: 16183531619906475296861224625027,
    991: 16839773100833956878604913215477,
    992: 17522282609145324707635966077022,
    993: 18232098083140097717852712346115,
    994: 18970297947002453464660671155990,
    995: 19738002669751617842096992232436,
    996: 20536376383452971700767593594021,
    997: 21366628562913781584556907794729,
    998: 22230015769169865076825741905555,
    999: 23127843459154899464880444632250,
    1000: 24061467864032622473692149727991,
    1001: 25032297938763929621013218349796,
    1002: 26041797385576000582369625213281,
    1003: 27091486754099167408984061096127,
    1004: 28182945621039436811282417218990,
    1005: 29317814852360484763188469380980,
    1006: 30497798951058731380716134731126,
    1007: 31724668493728872881006491578226,
    1008: 33000262659235183814081519827753,
    1009: 34326491852926110526276105821510,
    1010: 35705340429956356495500048880518,
    1011: 37138869521411924622451440267117,
    1012: 38629219967069644267226780200798,
    1013: 40178615358763694337831877170404,
    1014: 41789365198477765393682507986660,
    1015: 43463868175432916528376380161993,
    1016: 45204615566598118821992112719830,
    1017: 47014194765213080671467587361162,
    1018: 48895292942081479136595740785155,
    1019: 50850700844567331975836762416180,
    1020: 52883316738408211899530127054215,
    1021: 54996150497646497195116039121846,
    1022: 57192327848174163803231700285962,
    1023: 59475094770587936660132803278445,
    1024: 61847822068260244309086870983975,
    1025: 64314010106747559065438412709786,
    1026: 66877293730881687431325192921834,
    1027: 69541447366121616918816177545634,
    1028: 72310390310983979753319152713934,
    1029: 75188192227619293524858181464065,
    1030: 78179078837859260757658669457252,
    1031: 81287437832327804842152878336251,
    1032: 84517825000485590628268677129623,
    1033: 87874970589764795726619149717517,
    1034: 91363785902248291467082481888195,
    1035: 94989370137655453801161398756590,
    1036: 98757017491716010698603869808070,
    1037: 102672224519343960454073227246547,
    1038: 106740697772366151410092496101554,
    1039: 110968361721914939732387042839470,
    1040: 115361366975961956826368092270559,
    1041: 119926098802850790583643914139778,
    1042: 124669185972080868004022654618279,
    1043: 129597509924003418690815024769614,
    1044: 134718214280513689012974236132740,
    1045: 140038714709261994367964528304147,
    1046: 145566709154360370820516947589011,
    1047: 151310188447031979898125505211430,
    1048: 157277447310137702096803724432844,
    1049: 163477095771019024080265786609550,
    1050: 169918070997619096807349078318498,
    1051: 176609649573385253852206425342508,
    1052: 183561460227017093724267411668558,
    1053: 190783497033705025399011223174627,
    1054: 198286133105105766051740791002035,
    1055: 206080134785924286913455951259466,
    1056: 214176676375616994965530422655441,
    1057: 222587355394399185288134561600051,
    1058: 231324208413431926871476886628488,
    1059: 240399727469780275150398352541295,
    1060: 249826877087477024806306436682550,
    1061: 259619111926794902903903858282467,
    1062: 269790395084626208521306859330203,
    1063: 280355217069693265922512204254601,
    1064: 291328615477166797747643128851965,
    1065: 302726195388153340970512449363108,
    1066: 314564150520428320398942429589829,
    1067: 326859285157739328217944658021195,
    1068: 339629036885985812650521091739503,
    1069: 352891500165597792693064105229860,
    1070: 366665450770488753893927654278831,
    1071: 380970371125047658469252263285168,
    1072: 395826476571763477972460354798893,
    1073: 411254742603244027745802489871124,
    1074: 427276933093600703409672633110750,
    1075: 443915629565423279460548833975619,
    1076: 461194261529865886819548193737883,
    1077: 479137137938708024340405275972933,
    1078: 497769479788644748304553495300446,
    1079: 517117453919499510741582247311995,
    1080: 537208208049543370281513128274546,
    1081: 558069907092647074919064078269009,
    1082: 579731770803589829653889090465310,
    1083: 602224112799502127836867703068534,
    1084: 625578381007131993715400129218655,
    1085: 649827199587396195485096741151797,
    1086: 675004412390512738195023734124239,
    1087: 701145127996910209394091171983043,
    1088: 728285766401075776846633724874013,
    1089: 756464107397538946738052845597325,
    1090: 785719340730295196686468011045384,
    1091: 816092118069154575020287144949660,
    1092: 847624606878758096201928227674051,
    1093: 880360546248341702038727418718373,
    1094: 914345304752746677204951178080640,
    1095: 949625940417679322961779585842763,
    1096: 986251262864814583017230902369159,
    1097: 1024271897715020987348060381346241,
    1098: 1063740353330761125682320075116819,
    1099: 1104711089981595892462307006170625,
    1100: 1147240591519695580043346988281283,
    1101: 1191387439655339764253910592315288,
    1102: 1237212390925574690626025966996290,
    1103: 1284778456452494990829233226377379,
    1104: 1334150984591030161739618104847170,
    1105: 1385397746569649033264079085023363,
    1106: 1438589025231051837956193683375282,
    1107: 1493797706983703451005350179037500,
    1108: 1551099377078977592324977502565855,
    1109: 1610572418332734533482318570551190,
    1110: 1672298113414349146588255526290127,
    1111: 1736360750830546535004742869861557,
    1112: 1802847734735894350158767668809929,
    1113: 1871849698706449115822481531031302,
    1114: 1943460623617864164855763103650900,
    1115: 2017777959774244383161311335135412,
    1116: 2094902753439183950276117590000925,
    1117: 2174939777925753277977786731439319,
    1118: 2257997669407716887103312005936867,
    1119: 2344189067619971039484826726136835,
    1120: 2433630761622095504505007624351926,
    1121: 2526443840805024325560621670846260,
    1122: 2622753851327163276606626468293628,
    1123: 2722690958172823755991785784326387,
    1124: 2826390113032612069265970456163500,
    1125: 2933991228212416784843441604124699,
    1126: 3045639356784883554548008634432380,
    1127: 3161484879204764376319516386806829,
    1128: 3281683696617285755657387337131749,
    1129: 3406397431096706053660787897070925,
    1130: 3535793633060536116646611744883745,
    1131: 3670045996113488118329838058723628,
    1132: 3809334579584105681944821254585338,
    1133: 3953846039026223475533484851711932,
    1134: 4103773864966917551549475742004630,
    1135: 4259318630192449100691154502765975,
    1136: 4420688245873885709566584952625897,
    1137: 4588098226844616747507844508037264,
    1138: 4761771966352875646576237849731855,
    1139: 4941941020623653451737160975884815,
    1140: 5128845403576048431946742302750170,
    1141: 5322733892054158457915227866236060,
    1142: 5523864341942100491068450472029219,
    1143: 5732504015546648477080676455520535,
    1144: 5948929920644332374606657683899745,
    1145: 6173429161603651508297858791951031,
    1146: 6406299303007341112943259722223788,
    1147: 6647848746214407376439536432805536,
    1148: 6898397119316930779355317551024978,
    1149: 7158275680962446691834888697663475,
    1150: 7427827738529064471293660118664110,
    1151: 7707409081157399483953096394984678,
    1152: 7997388428160886234821473483000555,
    1153: 8298147893354134143293856722998488,
    1154: 8610083465857701451154337181278065,
    1155: 8933605507957017621037375468973282,
    1156: 9269139270613202791504126859283685,
    1157: 9617125427244236129299819591578718,
    1158: 9978020626416337178370164768812546,
    1159: 10352298064107568778430054733760345,
    1160: 10740448076228572334937735566562385,
    1161: 11142978752109030998555590333304243,
    1162: 11560416569682950887414131083801684,
    1163: 11993307053131181401163436777097233,
    1164: 12442215453765791987839842332792770,
    1165: 12907727454968012800119940123354311,
    1166: 13390449902019461518054086533162960,
    1167: 13891011557695348536983250121102793,
    1168: 14410063884518310798493113995825913,
    1169: 14948281854602503175542820411276425,
    1170: 15506364788049610799716682308517542,
    1171: 16085037220891570656183958875514689,
    1172: 16685049803609043819824168449851071,
    1173: 17307180231290097851615771678718278,
    1174: 17952234206530182283975172821446800,
    1175: 18621046436212348314484589328413725,
    1176: 19314481663345819649385158162679300,
    1177: 20033435735181507108244024178275807,
    1178: 20778836708864920831259413450679734,
    1179: 21551645995930215818617016034137500,
    1180: 22352859546983857840754489692613399,
    1181: 23183509077972665661421886007454584,
    1182: 24044663339478824029548767493555588,
    1183: 24937429430533921473492651656959612,
    1184: 25862954158495203059166455452470495,
    1185: 26822425446580095904068198565803164,
    1186: 27817073790709723558345700246365971,
    1187: 28848173767368633057992125893483779,
    1188: 29917045594246378653834785571179351,
    1189: 31025056745487001593014803461929555,
    1190: 32173623623434883211416744742294747,
    1191: 33364213288829995905464566634140396,
    1192: 34598345251472305106432161856883007,
    1193: 35877593323444056632515580254383154,
    1194: 37203587537049994338271609307035630,
    1195: 38578016129709269105524749061283955,
    1196: 40002627598109003613035027587346239,
    1197: 41479232824008249429294178038617951,
    1198: 43009707274162500911950054844789890,
    1199: 44595993276923101114218051405894000,
    1200: 46240102378152881298913555099661657,
    1201: 47944117779189310556261099429006223,
    1202: 49710196859679394486867802358932901,
    1203: 51540573788206651013836802198036893,
    1204: 53437562223729812777303406841914935,
    1205: 55403558110955564979344325681437822,
    1206: 57441042572873737644094937785113022,
    1207: 59552584903793044889004529388335732,
    1208: 61740845666328821093587961517238033,
    1209: 64008579895911365238424857597692590,
    1210: 66358640416504598253672231293216761,
    1211: 68793981271349892486345394543503614,
    1212: 71317661272679283934970057444157431,
    1213: 73932847674475963853859804733408932,
    1214: 76642819972498112301511348487927130,
    1215: 79450973835924928534740056571220837,
    1216: 82360825175131287067719845184002304,
    1217: 85376014350249959857626768802856615,
    1218: 88500310525337959944194241004565748,
    1219: 91737616173126446538485123122674660,
    1220: 95091971735501962459496140992085663,
    1221: 98567560445040729668418191983592407,
    1222: 102168713313097495533124764187939944,
    1223: 105899914290136190948927875636615483,
    1224: 109765805604181632042444034426405625,
    1225: 113771193283469872120310539095739833,
    1226: 117921052869579803514689801523449638,
    1227: 122220535327540435729044764084697099,
    1228: 126674973159627164610485151798391797,
    1229: 131289886729786527240095013237443045,
    1230: 136070990805862651658706033366694460,
    1231: 141024201327040104811696041691045190,
    1232: 146155642404167375009402954907061316,
    1233: 151471653560883058451095421311451141,
    1234: 156978797223733228787865722354959930,
    1235: 162683866469743733376335192519362494,
    1236: 168593893040195573779320686453020964,
    1237: 174716155629645388794651866300906835,
    1238: 181058188459536679140275000227478496,
    1239: 187627790146061111217741961494883890,
    1240: 194433032872253346998515292619988830,
    1241: 201482271874637706375741021005730181,
    1242: 208784155255090933098578892158986338,
    1243: 216347634128942766400406396453655835,
    1244: 224181973120705296790445342451587490,
    1245: 232296761219203590802475861123264133,
    1246: 240701923004274209788971782007579802,
    1247: 249407730257605432130910077287592727,
    1248: 258424813970713646981839124047488243,
    1249: 267764176763484957967824140618533500,
    1250: 277437205727159975794000686688315348,
    1251: 287455685706103555386947650491244181,
    1252: 297831813033180334721514504126791124,
    1253: 308578209734051855476222280888835192,
    1254: 319707938216222310789920115620477565,
    1255: 331234516459188101998422700026723439,
    1256: 343171933722591949005782567849433641,
    1257: 355534666789845852070090701405470932,
    1258: 368337696765269337188595637416276068,
    1259: 381596526443390734228095202493032600,
    1260: 395327198269680365975835178420652411,
    1261: 409546312912626108164576640399383898,
    1262: 424271048467724485839916892830607059,
    1263: 439519180314644983035319377172158032,
    1264: 455309101649532274915393819410766690,
    1265: 471659844715141371979173526935980437,
    1266: 488591102752254955447569352295355812,
    1267: 506123252696611256922641286254645760,
    1268: 524277378646375504218896129395592376,
    1269: 543075296126019045035073055561928520,
    1270: 562539577173328634024088141916141596,
    1271: 582693576277154906994867051360796655,
    1272: 603561457194424687753064451343608383,
    1273: 625168220675887416175494833282535136,
    1274: 647539733131042629585359752478706350,
    1275: 670702756263704072335812679441391888,
    1276: 694684977710697693392039019806832594,
    1277: 719515042717266582828863521396088515,
    1278: 745222586883866905899271646915240282,
    1279: 771838270020186251303063741763018130,
    1280: 799393811143400700904158178331205389,
    1281: 827922024658910558926936487548336568,
    1282: 857456857763058308684876665745077292,
    1283: 888033429108637280324653641355847207,
    1284: 919688068775347054572190680423598070,
    1285: 952458359588743164917093657911776850,
    1286: 986383179832665621554422059019604497,
    1287: 1021502747401614623677846147487591813,
    1288: 1057858665441074072255055670604124719,
    1289: 1095493969525365696982675003469664810,
    1290: 1134453176424250386882487822532585142,
    1291: 1174782334511180318623311370757902964,
    1292: 1216529075867847432892383159101984374,
    1293: 1259742670141472479018316728428818781,
    1294: 1304474080213136065603158197122179375,
    1295: 1350776019737370796417180820702333527,
    1296: 1398703012615213588677365804960180341,
    1297: 1448311454464961662889458094993182194,
    1298: 1499659676156986538068572255824972432,
    1299: 1552808009481139790520320395733292300,
    1300: 1607818855017534550841511230454411672,
    1301: 1664756752283809987147800849591201736,
    1302: 1723688452234384707674372422071320679,
    1303: 1784682992189681523983975379146100758,
    1304: 1847811773275862853601073393199008865,
    1305: 1913148640458255774876416600453369682,
    1306: 1980769965254371045106648307068906619,
    1307: 2050754731215233987976941410834180457,
    1308: 2123184622266649887649796215921782211,
    1309: 2198144114005025303125952328225613580,
    1310: 2275720568045462559712283145467243327,
    1311: 2356004329523040680859896842728890474,
    1312: 2439088827851495409213115816339495726,
    1313: 2525070680846917026164254568053937634,
    1314: 2614049802327600836872111661056230165,
    1315: 2706129513304814950403979441635984290,
    1316: 2801416656882996994241981980679918559,
    1317: 2900021716991759392273170147031719072,
    1318: 3002058941076075680836616507226015622,
    1319: 3107646466875142011769945929778234485,
    1320: 3216906453424662618200536823961141148,
    1321: 3329965216421699826558324552595808770,
    1322: 3446953368095762574438358199469775528,
    1323: 3568005961734486838351757966808790919,
    1324: 3693262641017091556254336031236632750,
    1325: 3822867794313779335421691039194332368,
    1326: 3956970714114397433384120384166003416,
    1327: 4095725761754986283464866437718755283,
    1328: 4239292537616325490949332681096528358,
    1329: 4387836056974246172531213471126988170,
    1330: 4541526931687319371792477450694975225,
    1331: 4700541557913558825461268913956492487,
    1332: 4865062310053998559115610911870100035,
    1333: 5035277741127427794082646196764289585,
    1334: 5211382789787193810929017395424321210,
    1335: 5393578994197824268512706677957552625,
    1336: 5582074712996280787878705083147454523,
    1337: 5777085353569942323599828874448120571,
    1338: 5978833607890937159258923653545207827,
    1339: 6187549696154203668120613167259109435,
    1340: 6403471618474669930531089742522848797,
    1341: 6626845414907208756853259936695984136,
    1342: 6857925434061555771629308454994509373,
    1343: 7096974610593182332652154711768629954,
    1344: 7344264751860200848154682253520601870,
    1345: 7600076834045756410267481267000412856,
    1346: 7864701308055034793828023244287340980,
    1347: 8138438415506002236313232141990462682,
    1348: 8421598515143296812402544776496284973,
    1349: 8714502420015324706702901500511538625,
    1350: 9017481745765587687202719206979752339,
    1351: 9330879270400591290587334955958115107,
    1352: 9655049305908367725798746534773552348,
    1353: 9990358082113704664098849646925432237,
    1354: 10337184143168612691406936474627379320,
    1355: 10695918757089402353832391602114778863,
    1356: 11066966338764988954966020552846311185,
    1357: 11450744886874712432979257653673465667,
    1358: 11847686435168064074325478460954986607,
    1359: 12258237518573265193633495987026371935,
    1360: 12682859654616659385819889316805008574,
    1361: 13122029840650374087829702479479965035,
    1362: 13576241067401694028191547060980833568,
    1363: 14046002849374084164798517831067165046,
    1364: 14531841772646818920248481411605550560,
    1365: 15034302060637734370093170532411179780,
    1366: 15553946158411737537905952886830918329,
    1367: 16091355336136399592075372322853441977,
    1368: 16647130312305245611392419213169232605,
    1369: 17221891897369251284144496300865473815,
    1370: 17816281658437585657529146257903261665,
    1371: 18430962605729818628447970674590396131,
    1372: 19066619901483662703451906966061889217,
    1373: 19723961592044861669045607586672623550,
    1374: 20403719363889095930868650315257219250,
    1375: 21106649324349767740001100592550916016,
    1376: 21833532807850282420908580590825862986,
    1377: 22585177208464977793681819296712788065,
    1378: 23362416839659197789401547387242312544,
    1379: 24166113822086183031380235679888630795,
    1380: 24997159000346486985219767235597236100,
    1381: 25856472889644547994140059803514309099,
    1382: 26745006653306882839626895694957692242,
    1383: 27663743112157144914230446319916689190,
    1384: 28613697786775039130057416743650633105,
    1385: 29595919973698836617070193875375888205,
    1386: 30611493856665016404478212802210021309,
    1387: 31661539654013410832232951778996345076,
    1388: 32747214803422179685312303680676279243,
    1389: 33869715185174019207110095647396061120,
    1390: 35030276385193261591559928994266853030,
    1391: 36230174999132974647956742131787699078,
    1392: 37470729978831867653000833781535492047,
    1393: 38753304022502786601002774984625192104,
    1394: 40079305010057880061198034072619085310,
    1395: 41450187485020176719746625583516317963,
    1396: 42867454184517379844972195257339462150,
    1397: 44332657618901196005888853882051385939,
    1398: 45847401702584520468158717245312104000,
    1399: 47413343437739346154537960139775251600,
    1400: 49032194652550394774839040691532998261,
    1401: 50705723795773236966373450556265512689,
    1402: 52435757789401123913939450130086135644,
    1403: 54224183941301948277230817879517159495,
    1404: 56072951919745741389655873424027752720,
    1405: 57984075791803952210030966295696158116,
    1406: 59959636127664498822125654803605200455,
    1407: 62001782172971294457628166694777458740,
    1408: 64112734091363688056165357762141754716,
    1409: 66294785279460087023332346767177823090,
    1410: 68550304756601011890673498202891728627,
    1411: 70881739631740035679525259959146526016,
    1412: 73291617649946553739726907624791770380,
    1413: 75782549821062183481895201583751205263,
    1414: 78357233133132880842076215608511229415,
    1415: 81018453353321656721019131504035339537,
    1416: 83769087919092159661630333467319344902,
    1417: 86612108922541440552472192615179632742,
    1418: 89550586190851013626818983550558814889,
    1419: 92587690465918960312381724727166445110,
    1420: 95726696686332376146505918443171660625,
    1421: 98970987374939026118276437676742560264,
    1422: 102324056135379743432459471263142178485,
    1423: 105789511261048976512902596439531532566,
    1424: 109371079460060057837671640558228717300,
    1425: 113072609699904337559514844445146843472,
    1426: 116898077175609399692092533607036637857,
    1427: 120851587405321266865514819340648620862,
    1428: 124937380457358912643772141796859437854,
    1429: 129159835312916652764103424563956670300,
    1430: 133523474368721196662101633251149823925,
    1431: 138032968084085429989744342641002104875,
    1432: 142693139776940493084095678732486636969,
    1433: 147508970573571548730224671300676243591,
    1434: 152485604516930928407097683383484266510,
    1435: 157628353838555246722760639034336216136,
    1436: 162942704399270720489853224525723269795,
    1437: 168434321304033467550147269349447360294,
    1438: 174109054696419141315515890296286539118,
    1439: 179972945738449034728553750103340839325,
    1440: 186032232781617921513478910563182232444,
    1441: 192293357735172557401982780429019456969,
    1442: 198762972637879108865432799270626669004,
    1443: 205447946439712986100137659510287259781,
    1444: 212355372000105810413242676805207816705,
    1445: 219492573309591728816879034317080350983,
    1446: 226867112941909191440813277312570747145,
    1447: 234486799743834826784604048875528356971,
    1448: 242359696770253388472695000770509170206,
    1449: 250494129472202113601016657658116885375,
    1450: 258898694145869442049569648660373941152,
    1451: 267582266650777119653998333871688332247,
    1452: 276554011405631474170238269248906446792,
    1453: 285823390670594346502222808229127105074,
    1454: 295400174124997022998049389765214784995,
    1455: 305294448749801797154111873648107967492,
    1456: 315516629024405747970164359073870491229,
    1457: 326077467447680222173319384811207626600,
    1458: 336988065393447621514574974879775699372,
    1459: 348259884310914705271679879631949049780,
    1460: 359904757280909011630794460361074410538,
    1461: 371934900939102477916959218389244857418,
    1462: 384362927777754206102413138268506970021,
    1463: 397201858837862893052822862772992037235,
    1464: 410465136803989050790556876831592919085,
    1465: 424166639514388116438037562729473373486,
    1466: 438320693899488240621648045435196959242,
    1467: 452942090362151303283202948578566379295,
    1468: 468046097613572904390385124958730619192,
    1469: 483648477979107092056857426409232236010,
    1470: 499765503188744811845488653259134061244,
    1471: 516413970667431889729975411863080081224,
    1472: 533611220340883210895592492267492392503,
    1473: 551375151973035052959106187501778547015,
    1474: 569724243051777714078869714336553502625,
    1475: 588677567240126095472954965375170347997,
    1476: 608254813410517219620274841577537789254,
    1477: 628476305280471269092869681239382035111,
    1478: 649363021668417110482089106581996800736,
    1479: 670936617389064931646215631627734512060,
    1480: 693219444808308092528746108408911793239,
    1481: 716234576078254109447577888083725273959,
    1482: 740005826073621415936329176309708825539,
    1483: 764557776051394742131574284792974302805,
    1484: 789915798056308219059157433980611758115,
    1485: 816106080095422250986408555099636706156,
    1486: 843155652105778433840074131252109568468,
    1487: 871092412739856974449839116812405949463,
    1488: 899945156994323847635597208986502059289,
    1489: 929743604708340998940330812008055415670,
    1490: 960518429958522963981451968247615571768,
    1491: 992301291378458055449596203783102865285,
    1492: 1025124863431572512298240504372933893698,
    1493: 1059022868667002481099668362066093137208,
    1494: 1094030110989052198741424671895432081910,
    1495: 1130182509971758083662737515471154158801,
    1496: 1167517136251048459523457118438435734632,
    1497: 1206072248027988195015615498189010425646,
    1498: 1245887328717627537181110407053143579875,
    1499: 1287003125779035759903231323132670516000,
    1500: 1329461690763193888825263136701886891117,
    1501: 1373306420616547671126845059808771245199,
    1502: 1418582100279183135137313919163744611210,
    1503: 1465334946617783561814630036179107930696,
    1504: 1513612653734759530017526259861629678205,
    1505: 1563464439696213993716384678301014319431,
    1506: 1614941094722713228367155822930278965324,
    1507: 1668095030888183105149797247519563263487,
    1508: 1722980333373639710221714255936544610213,
    1509: 1779652813323895051112691937493275900640,
    1510: 1838170062356853750560836014387165897751,
    1511: 1898591508776536523215092101916644734126,
    1512: 1960978475542532205781057345396110080746,
    1513: 2025394240050193548750246784190116959083,
    1514: 2091904095777554301862779830720186765825,
    1515: 2160575415856657801620130127396601613839,
    1516: 2231477718628751807313395954393627156678,
    1517: 2304682735244622286166458817442330457493,
    1518: 2380264479373211819043135033180865953593,
    1519: 2458299319083597933290739975588639913960,
    1520: 2538866050967394665741511337736337646822,
    1521: 2622045976570688763353306228619701197220,
    1522: 2707922981206731940550655607258234921458,
    1523: 2796583615222784382740474040856321114152,
    1524: 2888117177796744121961996863481080757250,
    1525: 2982615803341503976179051696005120224577,
    1526: 3080174550597354460133578989992600710402,
    1527: 3180891494495199523837557418419727460583,
    1528: 3284867820875874297854866890890114734440,
    1529: 3392207924153452428300151849140308700620,
    1530: 3503019508013107340706503153715459439135,
    1531: 3617413689236849218690486699230663550120,
    1532: 3735505104753300028632631618647052984126,
    1533: 3857412022010595043668172932897782160438,
    1534: 3983256452774513571402317362452698824910,
    1535: 4113164270457046596687344259862579939532,
    1536: 4247265331083807518632379721321456268679,
    1537: 4385693598011986873811172464601561040968,
    1538: 4528587270513945762405321738705440092603,
    1539: 4676088916345038581429933773569294261235,
    1540: 4828345608417856657751813260670405103571,
    1541: 4985509065708793590462102906287902242693,
    1542: 5147735798526653777473353718656776051935,
    1543: 5315187258276961029029844229698454778001,
    1544: 5488029991859677773715074283837789258005,
    1545: 5666435800842220652541448314024017081118,
    1546: 5850581905553958890153341953182905874297,
    1547: 6040651114252811450773802339294340809537,
    1548: 6236831997519121462431059121804263835744,
    1549: 6439319068036685669987130768251283335700,
    1550: 6648312965925656816271400679772663779731,
    1551: 6864020649797022030147590897007762961557,
    1552: 7086655593703494823378002063833638733692,
    1553: 7316437990166946592699616833531354911573,
    1554: 7553594959467950148686513765206276332400,
    1555: 7798360765388617440490476800142578927168,
    1556: 8050977037605691145961262617379106893607,
    1557: 8311693000936800120986617647413681760089,
    1558: 8580765711648916968128569908862807858077,
    1559: 8858460301044367459544239649173485609090,
    1560: 9145050226546241655095435675456471213374,
    1561: 9440817530511750873400887128525102883050,
    1562: 9746053107008968945969854946579275550253,
    1563: 10061056976799496323982724378320247274070,
    1564: 10386138570776897699583240005533846228720,
    1565: 10721617022118294111300879958656795681727,
    1566: 11067821467414245473548388055474400555521,
    1567: 11425091357050045737330444087123696839842,
    1568: 11793776775119777282986614097061549565288,
    1569: 12174238769162940693809364157051309012420,
    1570: 12566849690022197996332017608789608083314,
    1571: 12971993542129749223451407990577313551957,
    1572: 13390066344539111423681390555352209300441,
    1573: 13821476503028593889295382128265725457026,
    1574: 14266645193612571525140101316505187638875,
    1575: 14726006757806758281011522810861817647486,
    1576: 15200009110004083021400239371051767831673,
    1577: 15689114157328479953978540694207577474781,
    1578: 16193798232344933888778097136641377589301,
    1579: 16714552539015476523707617004948193446275,
    1580: 17251883612302523293667801378616630723938,
    1581: 17806313791832981004049940595952236488989,
    1582: 18378381710048954709565959117356034045626,
    1583: 18968642795283648606471174187975250526914,
    1584: 19577669790214200898277149916663590160135,
    1585: 20206053286156727802917377116665528100452,
    1586: 20854402273682788549513827814948445887987,
    1587: 21523344710050833153156141436233019518750,
    1588: 22213528103960970088758743797991090055558,
    1589: 22925620118156604193077050587843661667620,
    1590: 23660309190412159054931489112539937306848,
    1591: 24418305173462226026373553546995875617627,
    1592: 25200339994444087406536213435901662689794,
    1593: 26007168334442658312725535116810982082161,
    1594: 26839568328744494665699148030346372021260,
    1595: 27698342288425638399643940633635778570228,
    1596: 28584317443916730715736989648170031498488,
    1597: 29498346711208035625096160181520548669694,
    1598: 30441309481376795323275876211869020871017,
    1599: 31414112434139702720919278494304352579875,
    1600: 32417690376154241824102577250721959572183,
    1601: 33453007104814231206634568834252067530087,
    1602: 34521056298307127650200260789840693447039,
    1603: 35622862432723524773564047600591620474611,
    1604: 36759481727032834297334619181982868193810,
    1605: 37932003116763385216396036596083684144149,
    1606: 39141549257250138871243034824146893141432,
    1607: 40389277557338916599575631087245664105779,
    1608: 41676381244462492794128018619459154745923,
    1609: 43004090462031141893576046232131339283625,
    1610: 44373673400108265833414174147846823131033,
    1611: 45786437460370592180018097454654125762209,
    1612: 47243730456382146639125256475201485557926,
    1613: 48746941850241791637271332996842921594539,
    1614: 50297504026695610706485495279896144769485,
    1615: 51896893605837832676324724372468638684687,
    1616: 53546632795557357169752166455397628534844,
    1617: 55248290784921291361962286829338022618145,
    1618: 57003485179722265948521834701738678421349,
    1619: 58813883481452695155464304054870553436360,
    1620: 60681204611006611632952513664174735563434,
    1621: 62607220478448273296879161314388228250413,
    1622: 64593757600226437608809675150800761682315,
    1623: 66642698765254062321100804776702438717922,
    1624: 68755984751315254218264566880232672144875,
    1625: 70935616093304583685847007991159666098679,
    1626: 73183654904848448867540438473174344075670,
    1627: 75502226754904045590148716826986516533057,
    1628: 77893522600978716067675261669847531834806,
    1629: 80359800780661049649804576562965921695475,
    1630: 82903389063205132690374405132401276101050,
    1631: 85526686762960833261150746165714536727005,
    1632: 88232166916496002397533755182876654157205,
    1633: 91022378525311020523414800627504843113662,
    1634: 93899948866102260607570160618726171594330,
    1635: 96867585870588824684642587049077568806146,
    1636: 99928080576976385190854302771818195507418,
    1637: 103084309655193176038845274579543287624753,
    1638: 106339238008096180814672350296895542938848,
    1639: 109695921450910408688484641855278054316360,
    1640: 113157509471230885841519620824589853318260,
    1641: 116727248071985676199747488789041121983568,
    1642: 120408482699828936375465082551662467674163,
    1643: 124204661261505763907840490901149694071182,
    1644: 128119337230805474780434782661196752002675,
    1645: 132156172848797007097973143732608413596901,
    1646: 136318942420119455804633282594364118870621,
    1647: 140611535708182363299559887896839185406573,
    1648: 145037961432214389489427685180617331098024,
    1649: 149602350869185430852497209043356597608875,
    1650: 154308961563716222079735293780517268790662,
    1651: 159162181149181008424137378091161149008138,
    1652: 164166531283303096726173462843072095335410,
    1653: 169326671701640055015539018518705699850330,
    1654: 174647404392455113639317800019372440640580,
    1655: 180133677896574006306024799468201257241780,
    1656: 185790591735932160859341593488427864239206,
    1657: 191623400974625892978847721669762887224010,
    1658: 197637520916393159778610138707329017740693,
    1659: 203838531942564585384018857484505756167480,
    1660: 210232184494643970555920434333513855824223,
    1661: 216824404205799439501151597527348613503086,
    1662: 223621297185671858108005694276757667011704,
    1663: 230629155463036280733315769829856728366831,
    1664: 237854462590985052006674013310829555807395,
    1665: 245303899419437913541037116166052239846061,
    1666: 252984350039925153650180418719145316631826,
    1667: 260902907907734605017003921684746498516403,
    1668: 269066882146662257820916698151184555362272,
    1669: 277483804041759534527674431707495428212025,
    1670: 286161433725627991209904771339900788624872,
    1671: 295107767063974496251592243518106809957385,
    1672: 304331042746306921569506210339059205494747,
    1673: 313839749587822198745641666552447374489321,
    1674: 323642634048715381224461508374001874352425,
    1675: 333748707977320256428395802157949938763484,
    1676: 344167256583679214774724367914264615318981,
    1677: 354907846650332656774577448740278805781989,
    1678: 365980334987316359577499492665661423156220,
    1679: 377394877138559089794329589034333523822720,
    1680: 389161936347082504011271085636055422264324,
    1681: 401292292786621190557291178310378056588836,
    1682: 413797053067502749043669672231562125696658,
    1683: 426687660024856256094871226711613620285845,
    1684: 439975902797452509721828685778957458838000,
    1685: 453673927205721269316833783775783610703320,
    1686: 467794246437739506976775111608393022209053,
    1687: 482349752052240657962887540925835136720740,
    1688: 497353725307958208396664918548576500570384,
    1689: 512819848828887897371554062220903289550130,
    1690: 528762218615331555088826226879544901167527,
    1691: 545195356410872371074704272735369048924689,
    1692: 562134222435726415975597022642148002675881,
    1693: 579594228497218762288102882601473336765100,
    1694: 597591251488444805746508999799665944566660,
    1695: 616141647286498628873307956507246249662412,
    1696: 635262265061980727342758633558885467930686,
    1697: 654970462011837401470060834112028353314761,
    1698: 675284118527933869908522234215965152162520,
    1699: 696221653814122968723573796976021441661750,
    1700: 717802041964941442478681516751205185010007,
    1701: 740044828519446608929091853958115568986164,
    1702: 762970147504097887787893822256219849371554,
    1703: 786598738978990637725956554797278124357808,
    1704: 810951967102164263980984405643613443347625,
    1705: 836051838727132970358751925465426223753244,
    1706: 861921022549226171951777077723669881527186,
    1707: 888582868816776806015468170319304987709289,
    1708: 916061429623659935353293704664261165680563,
    1709: 944381479800161498529884419450242134471605,
    1710: 973568538419648201851756811932637866236071,
    1711: 1003648890939014757529114525804772812444576,
    1712: 1034649611991404349880377024889805948451966,
    1713: 1066598588850232767185892564930056790115492,
    1714: 1099524545584096492698787529446425808960485,
    1715: 1133457067922710638072138797746330685194571,
    1716: 1168426628854604371943988173648061076656356,
    1717: 1204464614977899904017040550277724793430409,
    1718: 1241603353626116601935133531509635427501801,
    1719: 1279876140791574929056038110412443745546155,
    1720: 1319317269869626093912245397158785002901753,
    1721: 1359962061247603108750056330533001022811146,
    1722: 1401846892763077891420050435782921418973709,
    1723: 1445009231056717653171633051674494164837538,
    1724: 1489487663845762650867366119648959070605125,
    1725: 1535321933144897017630429081796659362863565,
    1726: 1582552969462055408849028210050341395113316,
    1727: 1631222926997501215103529967929557707274660,
    1728: 1681375219875327721201833943152266777825092,
    1729: 1733054559437372469717283290044275542482740,
    1730: 1786306992630397874710969065930279993530728,
    1731: 1841179941518278501517284167616876198477309,
    1732: 1897722243951848075290887164802970670035779,
    1733: 1955984195429997917538913727371549522655006,
    1734: 2016017592186583869120124322228807307858970,
    1735: 2077875775538691593667272042037771337062872,
    1736: 2141613677532831241625032098057988491948517,
    1737: 2207287867926682588244859017849269988676029,
    1738: 2274956602545091757332316519809900057062533,
    1739: 2344679873050131347512524469147852330603290,
    1740: 2416519458166178053962910323080826683013954,
    1741: 2490538976402136614754617183069000726495038,
    1742: 2566803940314147020741857199436825485292885,
    1743: 2645381812353354350387072647528700656565179,
    1744: 2726342062344598291243970336667065409029860,
    1745: 2809756226643193380147979076327264594704745,
    1746: 2895697969018322254247325865029474629995508,
    1747: 2984243143312953802987213049129995837626487,
    1748: 3075469857931627124375487934417729522202013,
    1749: 3169458542208911724615579730356050273697000,
    1750: 3266292014712865596629588272103919719684547,
    1751: 3366055553539366839888542445766361166135204,
    1752: 3468836968654792543650918885868953010691040,
    1753: 3574726676346161983924385238571158169261725,
    1754: 3683817775839551051322373817401051497424420,
    1755: 3796206128149322537872121900182662159228241,
    1756: 3911990437222503807420937006192549828899684,
    1757: 4031272333444480835500888704164496363681686,
    1758: 4154156459574067047582172896269352052007031,
    1759: 4280750559177948266124532321685590709003370,
    1760: 4411165567636502893727652799725970383582718,
    1761: 4545515705795050750500358651870382988186314,
    1762: 4683918576336696329734155119529513589827658,
    1763: 4826495262955104262123827190438060829061153,
    1764: 4973370432407778155253526316242844344573385,
    1765: 5124672439532710418254508515826522600609941,
    1766: 5280533435313631955425559713040649796775465,
    1767: 5441089478081518530016413892489308199319929,
    1768: 5606480647942507023374562583725669127988521,
    1769: 5776851164524941659873115036048663114937695,
    1770: 5952349508140909502130662763236950728528684,
    1771: 6133128544460338166089749412557583307068767,
    1772: 6319345652798518839604562697210438023241550,
    1773: 6511162858120786446819766577778364926946013,
    1774: 6708746966871038378408979787060247103179750,
    1775: 6912269706733805859936155115580770892194054,
    1776: 7121907870442710074828422368434553047727682,
    1777: 7337843463751340976339671250105665526337260,
    1778: 7560263857685892761905455418833343917244062,
    1779: 7789361945202278758472065509114228369126600,
    1780: 8025336302373932563237571980294779250756300,
    1781: 8268391354240084356595173268406241855198176,
    1782: 8518737545447984082077112629884273268761094,
    1783: 8776591515826329476185591848477738781761689,
    1784: 9042176281031049610986292577509011838783245,
    1785: 9315721418408596645489064435708989370524469,
    1786: 9597463258226012911089716132158337004512929,
    1787: 9887645080421270408475092400425112950304770,
    1788: 10186517317031728481382143156507032880864866,
    1789: 10494337760463026157910800552509870425432010,
    1790: 10811371777765321805152346144711499265489879,
    1791: 11137892531088517813516189325593809889812108,
    1792: 11474181204492965595127263976240658672733891,
    1793: 11820527237297139926370474832027317722017807,
    1794: 12177228564148905369732416163985994571309670,
    1795: 12544591862012275060173347722472359244046903,
    1796: 12922932804266987528897386291108558284524280,
    1797: 13312576322123804564848753689176255125112158,
    1798: 13713856873564166596625513497299706749207160,
    1799: 14127118720018736045636750699617456881311725,
    1800: 14552716211005418005132948684850541312590849,
    1801: 14991014076953676011289439394970540421861988,
    1802: 15442387730448363289492676946827168544596921,
    1803: 15907223576132871507960364168750022280398562,
    1804: 16385919329518164710931105850817769087241385,
    1805: 16878884344951220830025131180984215659580858,
    1806: 17386539953003552219964871974446413826117272,
    1807: 17909319807547825412134603270711842061393357,
    1808: 18447670242798154252456532648116438246904907,
    1809: 19002050640597405466197703977606842321053540,
    1810: 19572933808242837304672225027800498209481360,
    1811: 20160806367149596270203427106156960870472824,
    1812: 20766169152660030143204019897118002904900168,
    1813: 21389537625315443974415368124511782893607123,
    1814: 22031442293915835855052489509763576677617505,
    1815: 22692429150702307814484325155610270148732358,
    1816: 23373060119006260978552660565770602425866730,
    1817: 24073913513719160198707702330267411589158084,
    1818: 24795584514946598972622146485353975132184526,
    1819: 25538685655220618058549873928821959736691905,
    1820: 26303847320654738379516399526912590943781620,
    1821: 27091718266436968469332058999564180929593866,
    1822: 27902966147067146894819024985472934375689121,
    1823: 28738278061756389082181003004910619210874204,
    1824: 29598361115418134291077518460315335403586750,
    1825: 30483942995692340860959609721949330792795099,
    1826: 31395772566456765282571775715588003409132613,
    1827: 32334620478291992350263579043602637456626234,
    1828: 33301279796379969106727880491661424703794769,
    1829: 34296566646329244238310747147664839490574535,
    1830: 35321320878433937019039707727760782467717785,
    1831: 36376406750887666110543978036746824592455791,
    1832: 37462713632488269058784695792011875893039111,
    1833: 38581156725384149030225659607573893303383795,
    1834: 39732677808428507338475836002967756141425565,
    1835: 40918246001723570069537718918088365292496141,
    1836: 42138858552953206373244111655326855421732185,
    1837: 43395541646119076823784928057386091817027588,
    1838: 44689351233312655065605577356497222364030752,
    1839: 46021373890173147491957400810472661489846635,
    1840: 47392727695699507038180086415408337440470086,
    1841: 48804563137103411752378288723762455918172986,
    1842: 50258064040409270440055764682612968116562013,
    1843: 51754448527527040549257397842950059733038281,
    1844: 53294970000543912137117431914902281880953875,
    1845: 54880918154001741201408795026747551723720527,
    1846: 56513620015948521242261975310131861303268895,
    1847: 58194441018574179427502571579696887885537742,
    1848: 59924786099263589386584792985885004002385100,
    1849: 61706100832922923109471297093651456522575000,
    1850: 63539872596459336786702846316806859551222764,
    1851: 65427631766318517268030842666066129833124679,
    1852: 67370952950009825188774721810114716943378422,
    1853: 69371456252574676254257996014226320491002233,
    1854: 71430808578980422724679205565325409535341535,
    1855: 73550724973449352362958820460243849915161295,
    1856: 75732969996760532083864127998517020593740791,
    1857: 77979359142591108905489195759391328910134418,
    1858: 80291760293993362744249170815935430293952943,
    1859: 82672095221134305875868191384112819286758200,
    1860: 85122341121455964860570648618210990142492639,
    1861: 87644532203446685358824902714882088097498633,
    1862: 90240761315246892123800470058435668367783935,
    1863: 92913181619346739765141403639335218061558813,
    1864: 95664008314668029507699782676107535163671365,
    1865: 98495520407358668662814112828386043342039288,
    1866: 101410062531664839123433827120996801871554118,
    1867: 104410046822283945831589672011997862390810762,
    1868: 107497954839640363519148716631132136446924023,
    1869: 110676339549566018509524250906452596245408440,
    1870: 113947827358908961175629034752466582068886470,
    1871: 117315120208635333752283890034504840221064086,
    1872: 120780997726033548383095326244127836720276225,
    1873: 124348319437674093156601079636921240241787962,
    1874: 128020027044824211921357710559027384266649000,
    1875: 131799146763063790207250005304405120478900361,
    1876: 135688791727897158862480183289001251910301886,
    1877: 139692164468205234207238255169848532611147557,
    1878: 143812559449433484718637448310794816419480218,
    1879: 148053365688463686582704780998822076298210405,
    1880: 152418069442171341962802939167993644252844977,
    1881: 156910256971726023650131079907915129924767174,
    1882: 161533617384748818044426030157299715901448409,
    1883: 166291945557499506406187783344043042314534878,
    1884: 171189145139326194380356742395417581059236130,
    1885: 176229231641671815409487530302217850452007387,
    1886: 181416335613995339496338175675291780004357523,
    1887: 186754705909030660706666553292223320927706878,
    1888: 192248713039873061921465120214608474899151280,
    1889: 197902852631451912018290889751846175017276700,
    1890: 203721748969018888548080806839085873409222663,
    1891: 209710158646353589075380551065506324110555541,
    1892: 215872974316462949034790068311792114803360768,
    1893: 222215228547627476999327377660931337519227930,
    1894: 228742097787726004875938672290676073251112495,
    1895: 235458906439851487440117948662414751746035425,
    1896: 242371131052313431017875037233367567350390976,
    1897: 249484404626207844803286441041017222801266718,
    1898: 256804521043823251651497040551112296246458295,
    1899: 264337439621241331244215401011574782781334700,
    1900: 272089289788583262011466359201428623427767364,
    1901: 280066375901447845568248481717977121765830398,
    1902: 288275182187185106927480861934498895209154826,
    1903: 296722377829749335448869068867067104949579464,
    1904: 305414822196978537321624475491324386207138350,
    1905: 314359570214253084228181897886953506729950270,
    1906: 323563877888595040544848710079341268243350278,
    1907: 333035207987381310882223234930566921371066351,
    1908: 342781235875958450915909855966319285240611144,
    1909: 352809855518564809408156722848357746339640390,
    1910: 363129185647086702371268910149149152584766993,
    1911: 373747576102299648025575523786476989131026713,
    1912: 384673614352373402423945044973430693054218643,
    1913: 395916132193550721591800039752382776657876433,
    1914: 407484212638044530444951338680763930621994820,
    1915: 419387196994336597778328640988515637140928750,
    1916: 431634692145202999016827948773519398239274548,
    1917: 444236578028937695571550278721551746219224713,
    1918: 457203015329395575643972370763403591173830810,
    1919: 470544453380630393038248327984084169870052370,
    1920: 484271638292061317700921219995285769876393805,
    1921: 498395621300264386957594139661914904785275330,
    1922: 512927767353652135411965358701027725220931707,
    1923: 527879763936476202951968110645920036905758794,
    1924: 543263630138763896173977941441058199308011100,
    1925: 559091725978980633941148481298313317618632967,
    1926: 575376761986396071222827176058084413124270202,
    1927: 592131809050322598728023510231907577504041350,
    1928: 609370308543590994569721078158344505753246979,
    1929: 627106082727829397306582084065079630894972195,
    1930: 645353345448318619933615779058934561872409372,
    1931: 664126713126409278261223804893870154281524038,
    1932: 683441216057704415059243252710086070145621992,
    1933: 703312310024435417776917212697059694728111811,
    1934: 723755888230689211116144545349876787252027480,
    1935: 744788293569381118983800284897623329523811384,
    1936: 766426331230110600455862693324715237997598939,
    1937: 788687281657286442867926694461098498097562065,
    1938: 811588913868164118077309502293768840003949925,
    1939: 835149499140701056072067990291237777551833530,
    1940: 859387825081405748983159033075649135425638325,
    1941: 884323210083634058665255574996164926064666511,
    1942: 909975518187071057883524303147934812769277935,
    1943: 936365174349429389500998978473009079907862954,
    1944: 963513180141695685953126594506747030515761180,
    1945: 991441129878565264237073831290682236831192947,
    1946: 1020171227196022316757683410004293870517496706,
    1947: 1049726302088348378540247976304143049122065214,
    1948: 1080129828417176195331669321286587690711167057,
    1949: 1111405941905549479818145590739116367242780000,
    1950: 1143579458630301665664240006110545368915059329,
    1951: 1176675894026428898785508782184245465533665048,
    1952: 1210721482417504396219216523662601652136179376,
    1953: 1245743197086563215894590527223118960072913202,
    1954: 1281768770902278683167516719540860443130307320,
    1955: 1318826717515654486899160825985211020969456836,
    1956: 1356946353142870071117550937780046987060960843,
    1957: 1396157818950341697358512735475562356104045295,
    1958: 1436492104058497734745724852296636956267964954,
    1959: 1477981069181214654702422049514025480619599210,
    1960: 1520657470918320177914639277247113472181645153,
    1961: 1564554986719042364085227429425894281463674979,
    1962: 1609708240534768479916261201915809290266567989,
    1963: 1656152829179975566133060952832169077820577902,
    1964: 1703925349420706097654088225457498186848567210,
    1965: 1753063425810487348828764073209783931216955698,
    1966: 1803605739294132404035202382553315081341190088,
    1967: 1855592056600414568536728473961840601327835478,
    1968: 1909063260445175620937659060948648856259756235,
    1969: 1964061380567012302624155966071951926644451875,
    1970: 2020629625618285067432170725261207144994992239,
    1971: 2078812415934808833368620144510853807585221613,
    1972: 2138655417208217715431844885515291279369574680,
    1973: 2200205575085644913617857845505033592721522553,
    1974: 2263511150722025533817142690940119270064496250,
    1975: 2328621757311014594133664064174539456980750339,
    1976: 2395588397621215290008835331658621643021314292,
    1977: 2464463502565134245725579502592034085209328984,
    1978: 2535300970829021467547395315846813198183591546,
    1979: 2608156209592513548223075037746157905702847505,
    1980: 2683086176367779880674969950590007819202341357,
    1981: 2760149421988673761061033114268064448054050548,
    1982: 2839406134781213852952373747778159055380262422,
    1983: 2920918185947567114582770377976676661508796149,
    1984: 3004749176196572544459946686955919368234128060,
    1985: 3090964483654736576896042159262866214940589314,
    1986: 3179631313092546273793802882159493889001969611,
    1987: 3270818746501886244063493400323024051287288941,
    1988: 3364597795061310125684361619251416376860936489,
    1989: 3461041452526908153028282986522280729367368365,
    1990: 3560224750087529486464584716859554522268776125,
    1991: 3662224812724162303217742306542356590926722479,
    1992: 3767120917114346857096063738777247515406335526,
    1993: 3874994551123597548057533501867770741416429535,
    1994: 3985929474926940257994009093217001343955328335,
    1995: 4100011783804831583821441379839563991285227198,
    1996: 4217329972658917930562969936711305445974785514,
    1997: 4337975002294315534109569503386742455494341143,
    1998: 4462040367516348205694592687945941817364967127,
    1999: 4589622167090968789784046573687400867942870250,
    2000: 4720819175619413888601432406799959512200344166,
    2001: 4855732917379000237574365609687488912697273143,
    2002: 4994467742183366148074839035447416380393781644,
    2003: 5137130903316893622770745464235084139384928426,
    2004: 5283832637599517075572081746564260420858901705,
    2005: 5434686247639634059061258993904042430607990074,
    2006: 5589808186334383050291570992756471405633041387,
    2007: 5749318143678144230778676663789672984169195116,
    2008: 5913339135941752405965378691599572441324623941,
    2009: 6081997597286587859405678030809218670282246785,
    2010: 6255423473879432172551153347179787953125682826,
    2011: 6433750320575743037411316728215679204642749660,
    2012: 6617115400240816052275556661314890288999332009,
    2013: 6805659785780163657391920602286596663406217911,
    2014: 6999528464952353007567067145415164276505069670,
    2015: 7198870448039506994791503590601126801607534137,
    2016: 7403838878452687162912842119176262318542314409,
    2017: 7614591146351445269661694564912786246445478891,
    2018: 7831289005358953156344654888013498638339711692,
    2019: 8054098692456299826324570548607480763080403880,
    2020: 8283191051141781691732068101840743191755759916,
    2021: 8518741657943308344041302580996941768179250799,
    2022: 8760930952374403498169602637389577451855415964,
    2023: 9009944370426700552244228695797096011740585251,
    2024: 9265972481694316138437595284729122693073711400,
    2025: 9529211130228034799395854632912272457677896880,
    2026: 9799861579219855238744997642818047729388291567,
    2027: 10078130659621135236933601810787303619515113811,
    2028: 10364230922800330115415428619787879783434758914,
    2029: 10658380797349150440403847607713189208549844510,
    2030: 10960804750148870398245267228037581609577682339,
    2031: 11271733451811500913798689538973402825112404379,
    2032: 11591403946613603138135282386492611425148475178,
    2033: 11920059827043660471886625110700606109457615243,
    2034: 12257951413087152938966999455842406831025654415,
    2035: 12605335936376788660643906067688568691477294599,
    2036: 12962477729338745637101954446070534143126297085,
    2037: 13329648419469265315863347103932314055721954884,
    2038: 13707127128879519866370496154104287110788727040,
    2039: 14095200679250350101462435045670967566714006190,
    2040: 14494163802342243065803242497250145705564482929,
    2041: 14904319356209789989230727462504226498494263931,
    2042: 15325978547273839186092526952960232758544597811,
    2043: 15759461158408637244144834830819680263402565217,
    2044: 16205095783205438232082764786847977319531548455,
    2045: 16663220066578357477963673318612506891057322162,
    2046: 17134180951882656619355889974597586372298980947,
    2047: 17618334934720173062514849536736413843694654543,
    2048: 18116048323611252751541173214616030020513022685,
    2049: 18627697507717313357328883548487129542980353125,
    2050: 19153669231803058848943059805108758933859747374,
    2051: 19694360878632389188479682121479772827588278091,
    2052: 20250180758997203961018562965051517467373563574,
    2053: 20821548409583589567679943310731809893410960813,
    2054: 21408894898885309715106534167513145969112337635,
    2055: 22012663141380091963647773040348591535494857021,
    2056: 22633308220189922777870335143856096247251187948,
    2057: 23271297718452433681930253947266040250043569734,
    2058: 23927112059636485682887466272819725468557276242,
    2059: 24601244857041242112722641487525252331485884885,
    2060: 25294203272724365584159904646608138971697036406,
    2061: 26006508386111487092631615069752229687889047419,
    2062: 26738695572545778772495897103306702147812265676,
    2063: 27491314892043320887814631666080168776331811888,
    2064: 28264931488526992879603605279805458570836160570,
    2065: 29060125999818842393508123538658855855869573724,
    2066: 29877494978678299986437859187588252356283557915,
    2067: 30717651325181215594079225685922159612710890246,
    2068: 31581224730742500897001026737587458361246031363,
    2069: 32468862134093174645484430948409904593113694670,
    2070: 33381228189530831120385246576357623531476650368,
    2071: 34319005747770990684777087747947525376490393829,
    2072: 35282896349735451425203004555804514075824949148,
    2073: 36273620733622647942922713748119798292462316154,
    2074: 37291919355614143333586997222803939193763027250,
    2075: 38338552924580739339245889549713324449360541521,
    2076: 39414302951161293776274047281093717842584188891,
    2077: 40519972311597190003244878215733219997449415843,
    2078: 41656385826715516924455731088372893657996361228,
    2079: 42824390856464396526209228476474575762774879465,
    2080: 44024857910414546084950481401735302373848095782,
    2081: 45258681274652091016547586287700221970008068755,
    2082: 46526779655498859083237494859206365034702358134,
    2083: 47830096840507894753763929606166424148960110424,
    2084: 49169602377193741528342591922356853935149504975,
    2085: 50546292269969157794099110029993948769746687671,
    2086: 51961189695772366269783089381199090558960547606,
    2087: 53415345738881696537662435419712492307334180478,
    2088: 54909840145427572963129830596638040418770704515,
    2089: 56445782098125235102442269204682620745124030885,
    2090: 58024311011765363351557172881384457469348901699,
    2091: 59646597350013928176910703744766844433767270677,
    2092: 61313843464087096107973721257849778294625405081,
    2093: 63027284453881919316292784641070835053831354052,
    2094: 64788189052158817856342546799691255570877518150,
    2095: 66597860532387544551063529093372826237515675728,
    2096: 68457637640884412378329010378860869685804024262,
    2097: 70368895553885073626926030071097479233359907864,
    2098: 72333046860214079886074787715712944920415424984,
    2099: 74351542570229833233029956235268391407949627875,
    2100: 76425873151741373195807749021080021459080291165,
    2101: 78557569593611742891613633197716231871513782517,
    2102: 80748204497781453174729297053600127492388932998,
    2103: 82999393200464827976246067679320326020971457938,
    2104: 85312794923291779902869927934730036659721510375,
    2105: 87690113955187845526792666366851401712801134274,
    2106: 90133100865806117918203480753613859038381596324,
    2107: 92643553751346063460833585063932351673594098859,
    2108: 95223319513616114811576859302283546424619314506,
    2109: 97874295173219406337291510865301717288885200445,
    2110: 100598429217765077170980775830078597915978709260,
    2111: 103397722986031225236603653787203378188231402292,
    2112: 106274232089029868642533106912359104776603150690,
    2113: 109230067868949174578477633685673008965957469120,
    2114: 112267398896973766514395710229044460157179222920,
    2115: 115388452511010134752244464747991318862444784689,
    2116: 118595516394371070307305070689995677519803374830,
    2117: 121890940196500635216372474879596908517840948778,
    2118: 125277137196849491653446187682001921308870438795,
    2119: 128756586013039456106279781429309224204637155235,
    2120: 132331832354485942225817194731144948296095338913,
    2121: 136005490822677526183628341619662696228169437779,
    2122: 139780246759343231332496879136294914183920566235,
    2123: 143658858143770305041408732118198629930850140819,
    2124: 147644157540568270666807354340091712330909224000,
    2125: 151739054099208903158067016467162544501125246216,
    2126: 155946535606706519753573960842521384418556790909,
    2127: 160269670594838620141199867367375227901178121673,
    2128: 164711610503343476443764262455655533446463188624,
    2129: 169275591900568786145109713871008667212574145360,
    2130: 173964938763083984897646967444489323060065487907,
    2131: 178783064815808295968062329270497666350416021621,
    2132: 183733475934247094438727208707795835845879643176,
    2133: 188819772610470713392617031395550078686410106988,
    2134: 194045652484512443040038057363040342445733893240,
    2135: 199414912942906199650168544999618866932966543484,
    2136: 204931453786129197483756438132982529754356479553,
    2137: 210599279966760972657750340621024569609658319243,
    2138: 216422504400217312716806872498425178952708753752,
    2139: 222405350849966070103844047835296998593257719870,
    2140: 228552156889181512949138540918848061266047740791,
    2141: 234867376940844824665120188180587152072518199582,
    2142: 241355585398350637585388084310633650150819331465,
    2143: 248021479828733108998565670865001643954560554353,
    2144: 254869884260680054932039940494913967190530868955,
    2145: 261905752559560083345100350260758248905652921875,
    2146: 269134171891745550301357546978902318483150550307,
    2147: 276560366280573537433149830945908221546675684073,
    2148: 284189700256347954756384460822072399114186994724,
    2149: 292027682602848348780952829894171946286185196525,
    2150: 300079970202875082019467410865495625479979094694,
    2151: 308352371985426287572392634796034918345831989966,
    2152: 316850852977169433649870812195036854291507911207,
    2153: 325581538460939500937426146405250734530774231825,
    2154: 334550718244066724977417207615678241114465752975,
    2155: 343764851039409631696645200323540686552303329604,
    2156: 353230568962043743490045985418104968175497835998,
    2157: 362954682144632903677995273534058279957414924705,
    2158: 372944183474588707707117294510467908715140736065,
    2159: 383206253456204090418195791785818308423831594945,
    2160: 393748265201029751587449904786884268416346918520,
    2161: 404577789549846859589538794509144411672022826612,
    2162: 415702600329676409598230534926593885982499170401,
    2163: 427130679749354783768755297437892949499654467597,
    2164: 438870223937296523272831771890659665602286473475,
    2165: 450929648625159134260052749493609306300370136632,
    2166: 463317594981220971649101966934064855005088490212,
    2167: 476042935597381937471938911243959272191670950572,
    2168: 489114780633797957215706040263930987465371910798,
    2169: 502542484125264022730810437527574105649622691760,
    2170: 516335650453567079927347553251246871212620557984,
    2171: 530504140990139261462232960508189648909724886170,
    2172: 545058080913453988432836606455557467047353067377,
    2173: 560007866205722361999363584087410496745060913524,
    2174: 575364170833565108914383039346175332072363129225,
    2175: 591137954117456209042263051672264094963902965317,
    2176: 607340468294858294890172396576637459876728673686,
    2177: 623983266282097051667127111749751355541610352255,
    2178: 641078209640152242143041148426227499209194350336,
    2179: 658637476749676716333547258428298949880301221655,
    2180: 676673571200691926609848235322274189175428592431,
    2181: 695199330402549141183113024435698489390907024630,
    2182: 714227934419889822186067591088150189762713935508,
    2183: 733772915040486600160233205517764582904605949651,
    2184: 753848165080998028345195047409661205734061410010,
    2185: 774467947936825933802831039011913166290856798904,
    2186: 795646907382423796556925927113569848920749045025,
    2187: 817400077628568283525440629036885986580578161120,
    2188: 839742893643273944545131128461036809985928936965,
    2189: 862691201743203249313515607587263855592485446510,
    2190: 886261270462600715344592984957682094231262687955,
    2191: 910469801706960959527768615813845716032362752763,
    2192: 935333942198826213870111109341848015258586306792,
    2193: 960871295223299296636466125655717340185883228697,
    2194: 987099932681053343467853379878084516482176109430,
    2195: 1014038407456819902258601282188003020164821077713,
    2196: 1041705766111542406799393149921058024912789843193,
    2197: 1070121561906592696806185003711836723976318646033,
    2198: 1099305868168664278558814578725663660095230751347,
    2199: 1129279292004177556899411779284367814322107068750,
    2200: 1160062988372259455129906418328374912794875140516,
    2201: 1191678674525592817234330378465180518007035567938,
    2202: 1224148644828669903250292851179037002332204681842,
    2203: 1257495785963229293609758350537517985043490101070,
    2204: 1291743592530906765707814604565428064732892610835,
    2205: 1326916183063388353539586696826007823016666575690,
    2206: 1363038316450618010620081932775702626766948267742,
    2207: 1400135408797883233268006240578157606704308520406,
    2208: 1438233550722879835539717164127729784341377881813,
    2209: 1477359525104141972742451850876428128946776467300,
    2210: 1517540825292515665993072463432902551892845533240,
    2211: 1558805673797653668641491334803497135876242089678,
    2212: 1601183041461816724044580259727354612842328867083,
    2213: 1644702667133581285344348736857245137869671730074,
    2214: 1689395077854376798567156661483099222514277324220,
    2215: 1735291609571106892437555774714449031725527460139,
    2216: 1782424428388448478757191595009703327418571383436,
    2217: 1830826552374771058174587388568897962322872702465,
    2218: 1880531873935975665104704330318867749822093808655,
    2219: 1931575182771919095318938056959674511017686068185,
    2220: 1983992189430464568754141912398798172706580941262,
    2221: 2037819549474585022525115674537508812727151594151,
    2222: 2093094888278340044956073813211683523416074682898,
    2223: 2149856826467952296650447653773869417501164619869,
    2224: 2208145006024624371311040214176565237134381870625,
    2225: 2268000117066162685610486257867691977952149636083,
    2226: 2329463925324911418747662088887963091854286975547,
    2227: 2392579300339947019867081675868949317697298397221,
    2228: 2457390244381942643492189138307718097264928854677,
    2229: 2523941922129582344692758164350149756471869195790,
    2230: 2592280691116887259141942758496845583141659899537,
    2231: 2662454132971310608073787558386111506684369385813,
    2232: 2734511085462965511444391934177140596906494183587,
    2233: 2808501675385869578994261445169376899379754972068,
    2234: 2884477352292623400907075579322579400861330771315,
    2235: 2962490923104486707892612022451087039141493329190,
    2236: 3042596587619376453548710860694923114675620792521,
    2237: 3124849974940885736970186673957557524827120772983,
    2238: 3209308180852011686602310843936272621314792055526,
    2239: 3296029806157884531966398832249411659082252110525,
    2240: 3385074996022409471869790373849802994298808805690,
    2241: 3476505480324367989101580130555189921672623462046,
    2242: 3570384615059176354982401320439389024740905215964,
    2243: 3666777424813166614813801947045518673161561892966,
    2244: 3765750646337939759592154130429553527537766985115,
    2245: 3867372773253042492891322334008521298830352179629,
    2246: 3971714101905938427653556222571377434088646307540,
    2247: 4078846778418982139592272233327190495676444439866,
    2248: 4188844846953860716858469962505733762730156946697,
    2249: 4301784299224742745702713528067084946594634381000,
    2250: 4417743125292169536796493320206228992803910550343,
    2251: 4536801365670538316236136117174461033288094273661,
    2252: 4659041164782862580763013973003868359053553220232,
    2253: 4784546825797351362566231731168417844332785838733,
    2254: 4913404866881227292111965728061869527659853830530,
    2255: 5045704078908103627757617096847635981526636026359,
    2256: 5181535584656163391837451036356625290841516214407,
    2257: 5320992899535329981545125277691916180855473998805,
    2258: 5464171993882588690437588095807084889323827738187,
    2259: 5611171356865613078294130300389571289206397311350,
    2260: 5762092062035869673687412904560243239930531635515,
    2261: 5917037834573419710379575999541430738890622626340,
    2262: 6076115120266708126452900640242923623341866228338,
    2263: 6239433156271728550695355451490575993085942292134,
    2264: 6407104043696079137218319509378718229702705761905,
    2265: 6579242822054578576274630855578948789533455298734,
    2266: 6755967545644295113522674510292835122483775946206,
    2267: 6937399361888054675782970897485983723264323011797,
    2268: 7123662591696737970806754341094737575112103730614,
    2269: 7314884811901951462222340761939935289641834289395,
    2270: 7511196939811964197947649707463044206175866380723,
    2271: 7712733319945142389521924617582058172801542180874,
    2272: 7919631812996487219317452100595913257543028088576,
    2273: 8132033887094289430962576814720449927838393960827,
    2274: 8350084711405357694774361105408889911972402015300,
    2275: 8573933252148757415018198504928925593185861873742,
    2276: 8803732371079513461579268567498022304249933730391,
    2277: 9039638926505285189617314422998964084970595438542,
    2278: 9281813876900616004271298745383250743059729594527,
    2279: 9530422387184993604151073155371828079705355168950,
    2280: 9785633937732631891816046069641124632254214557235,
    2281: 10047622436183602390848394841406802515973193043806,
    2282: 10316566332127702901769041143039403233989122380996,
    2283: 10592648734734255132957468343310308444321456043571,
    2284: 10876057533402872254341014560334244700946683620780,
    2285: 11166985521512132864360358955503173717957792328653,
    2286: 11465630523345040885726361109312137419668093929920,
    2287: 11772195524272142592252579142228927699835475405262,
    2288: 12086888804275213526126666074714236379441857513978,
    2289: 12409924074896520730686758323108856061617655222490,
    2290: 12741520619700810766902679602920740106349316265795,
    2291: 13081903438339372702369995825105861818651826992639,
    2292: 13431303394307778991751050067148151893379620506077,
    2293: 13789957366491217272065156663906255405414311071587,
    2294: 14158108404593693973445004415760318309772932242370,
    2295: 14536005888549817728742960090051403934327801222156,
    2296: 14923905692020358321733692442892587286459907678047,
    2297: 15322070350075326847761463298913968554265401515217,
    2298: 15730769231170936413643835624649288938501733002618,
    2299: 16150278713529481654471379166675899361510665760775,
    2300: 16580882366033921211442301450921091904365926280416,
    2301: 17022871133751761754598643267756804218108498650480,
    2302: 17476543528205726845562009156571175360531579106807,
    2303: 17942205822511650658087298129211531345495818175057,
    2304: 18420172251507067091174412069974707159021665744880,
    2305: 18910765216997070947078996545777114475682919623589,
    2306: 19414315498247211476154846356983916621521411447697,
    2307: 19931162467856441629277246980513463599759674413041,
    2308: 20461654313146490770914182133145338856645809727187,
    2309: 21006148263207456404192932627622104852595304280970,
    2310: 21565010821742923705373368869534441911701199887419,
    2311: 22138618005861522471365237940368652982888104075000,
    2312: 22727355590965521614482418924663783733921186781149,
    2313: 23331619361890843810727406215610806254135308857160,
    2314: 23951815370456759593096244705083096637451017834880,
    2315: 24588360199587493406897494649744406335205727290057,
    2316: 25241681234172046294108468111219387029991510514102,
    2317: 25912216938832713390963025920891990759428674050912,
    2318: 26600417142777051809706408361950504454660772072685,
    2319: 27306743331912438295458811467722364839525869129400,
    2320: 28031668948406848928849481174161195141360108410956,
    2321: 28775679697884097775242882020060349688803476984805,
    2322: 29539273864446490518541231137563989837057604952179,
    2323: 30322962633722685585711432023667002655631855893969,
    2324: 31127270424143511960418282768032077800615961592375,
    2325: 31952735226653572764265207581869821725011637243487,
    2326: 32799908953071669788426324706615644528794262188810,
    2327: 33669357793318419597396187557448074241909961160527,
    2328: 34561662581734899786701292837993789078148269659948,
    2329: 35477419172721767722086620675579581559062365395875,
    2330: 36417238825934036963035091771377814636876895938849,
    2331: 37381748601272582004301821355152191840543933044480,
    2332: 38371591763919473464910961559285225914454949449279,
    2333: 39387428199670427009917909560877277324279071654230,
    2334: 40429934840823983789090419362572880622618841036000,
    2335: 41499806102893531791299424581039874366426784160676,
    2336: 42597754332414930108684698464207986438238414531147,
    2337: 43724510266129315639709919648795164529190983190550,
    2338: 44880823501827658290753362113015735891775860228025,
    2339: 46067462981150790416506320013365490407603364278280,
    2340: 47285217484645973326080769865489605746387338228688,
    2341: 48534896139388582534016509015707084448606794509814,
    2342: 49817328939485198519236927086579980055136752412153,
    2343: 51133367279782285645165745517535680609133370052296,
    2344: 52483884503112733276871946748564813602003527319855,
    2345: 53869776461420824806590383880147822175719204551469,
    2346: 55291962091114697184508819760614991511857392669436,
    2347: 56751384003004060684283391440819878903446789803099,
    2348: 58249009087189871171927544609837628960380623034142,
    2349: 59785829133281790377677305788784327434428364970750,
    2350: 61362861466328639006942053695686748622617850877171,
    2351: 62981149598856648513992946515066172932792511110884,
    2352: 64641763899420155681002068750650481144652897951882,
    2353: 66345802278079465613952539750862814246981008871159,
    2354: 68094390889230939345801166300675543634997580023495,
    2355: 69888684852224948030989898005576415781403878920995,
    2356: 71729868990218182977254525351745038902483193889528,
    2357: 73619158587717925895914811729724245783180985354842,
    2358: 75557800167287273321320320811040130784252221919060,
    2359: 77547072285891979874115998945868567670402747044445,
    2360: 79588286351381543804941144999617740627898062871643,
    2361: 81682787459609412105690788920445375282931841060492,
    2362: 83831955252709738636327407566454519669269037443061,
    2363: 86037204799060994583504133500298291142599767525961,
    2364: 88299987495479913719532319572840702828357104994815,
    2365: 90621791992202763126914659986946872015595738278003,
    2366: 93004145141224771243446359569837640488487305606833,
    2367: 95448612968582727407224954007027627693270062216153,
    2368: 97956801671180298878693599735216669857785613237715,
    2369: 100530358638770501129135789786132580428696541463525,
    2370: 103170973501725013759939661850158896906366983382795,
    2371: 105880379205235666714568162057607929186246674835477,
    2372: 108660353110609438642727243903401536959027659486124,
    2373: 111512718124334720773264584058717478384571245088082,
    2374: 114439343855613415076071522953096149591716910973500,
    2375: 117442147803070664704054798350668120890654926300513,
    2376: 120523096571371667803183996442776155815729810091602,
    2377: 123684207118493113105268436573489685721321552781151,
    2378: 126927548034415307868377394917913546501247383867613,
    2379: 130255240852020056553944404306572055559539047530145,
    2380: 133669461390998803240347188535274022509125836065110,
    2381: 137172441135595483551688849972013947996581871778170,
    2382: 140766468647028954484433593096055372616292751308832,
    2383: 144453891011460794882135190497537058556764977948995,
    2384: 148237115324395707667015292482470242745754168289775,
    2385: 152118610212423719809411357105042520067307779240520,
    2386: 156100907393235880227548485941067592747534460439448,
    2387: 160186603274868212495995174730244824826286924759060,
    2388: 164378360595152301854136694694118079266206458932708,
    2389: 168678910102375098323537690529566365095195830119715,
    2390: 173091052278175313875346442702502205694341724313429,
    2391: 177617659103729195986746184184236646145304254737028,
    2392: 182261675870304487388520687355584130250935690880972,
    2393: 187026123035288047490867195922886699634867141186408,
    2394: 191914098124819930404162679326110679178204492902970,
    2395: 196928777684194703542432119373410255613845416290627,
    2396: 202073419277219465790162920942761564437025278844409,
    2397: 207351363535747401800832745531222095970123079470866,
    2398: 212766036260635806253027202800291886071043511130893,
    2399: 218320950575408346303872686615815518603736687265550,
    2400: 224019709133932919957689061390552862746031758458304,
    2401: 229866006383458830949778967121025947053151071434926,
    2402: 235863630884390155812442175854014517889393984836232,
    2403: 242016467688206145276344061824939391497289921344319,
    2404: 248328500774974299762177021852107412058234599633660,
    2405: 254803815551937407606287486346848530864431251682411,
    2406: 261446601414692355496335282873363983668020889836360,
    2407: 268261154372515934523018586706764224652758295238166,
    2408: 275251879739431193944393927980843975448015734231456,
    2409: 282423294892647160394499527988292633580813431968720,
    2410: 289780032100044965565638185282633831588088504297253,
    2411: 297326841418424633617945474627449518623223932967198,
    2412: 305068593664268994544312629723329236676843814611957,
    2413: 313010283458824435839645487672681448751536128120719,
    2414: 321157032349342507073515697424466804962980378707300,
    2415: 329514092008371775927573078641257544141430283832310,
    2416: 338086847513035826131406156272669425469096435441169,
    2417: 346880820706280914339971199061511110032851886967137,
    2418: 355901673642125591813707043622534952223283339280101,
    2419: 365155212116994575920151188842851740380508864908970,
    2420: 374647389289270354779812696943359199223073776527524,
    2421: 384384309389248455327267290257609074709972871788879,
    2422: 394372231521736030856900123129107963761511852907062,
    2423: 404617573563588459702218138566029837845857058362469,
    2424: 415126916158535023731030449746058156911457360217500,
    2425: 425907006811702486258611691435747829051036619210903,
    2426: 436964764086304546997571902667823798077679571339689,
    2427: 448307281905025750783203518734071850525930124835870,
    2428: 459941833958690501858441260833172834575927050017497,
    2429: 471875878224871422129752689802003581309719671216145,
    2430: 484117061599156426525236728117223720907832020184888,
    2431: 496673224641860608784678055946833883950031191035725,
    2432: 509552406443037374969583492229383313416835733059701,
    2433: 522762849608713268897451362983651906277382721179854,
    2434: 536313005371342643715460083111040042096768651944785,
    2435: 550211538827551788032090316191702467148009553891765,
    2436: 564467334306317355502338280181042531694130943361929,
    2437: 579089500870801016601654991798984624538203584674550,
    2438: 594087377957141194645081615027313378657219091976058,
    2439: 609470541153583610086244251156702088407546864564250,
    2440: 625248808123415184021445170239142357065496320226974,
    2441: 641432244675250690988723453000798446534275367015717,
    2442: 658031170984308451084537723836848917759126780943929,
    2443: 675056167968400361774985057979390540476824195499264,
    2444: 692518083822452741394297527894579793217444427279865,
    2445: 710428040715467841255717203419691810125435835218542,
    2446: 728797441653931534847387578562876222605215306007682,
    2447: 747637977515770665320414243823232108546943571791584,
    2448: 766961634259063882272862309538971496456501841189299,
    2449: 786780700309812582901493233837104883069651992252500,
    2450: 807107774133183849507621375104362485942528919417094,
    2451: 827955771992745105077858611205558631300937454362243,
    2452: 849337935902320652619232737317794449777545949179711,
    2453: 871267841775213384980863950063063429886904651528812,
    2454: 893759407775650814410526929963928966861696330836200,
    2455: 916826902877433240978780331677009554236212353692084,
    2456: 940484955634883423732306479679700600136395142799772,
    2457: 964748563171321607096873785043308907920748393645865,
    2458: 989633100390417258370972350733200785584553946028102,
    2459: 1015154329415899462551538855668088513315200292902465,
    2460: 1041328409265241672356796753836476758668568608962817,
    2461: 1068171905763073500068056689718618672673472054705623,
    2462: 1095701801700212541420510934836771894810436524644206,
    2463: 1123935507244352919801698227500042488236652668362464,
    2464: 1152890870608594412929146690100187865796230009117415,
    2465: 1182586188984146757378861272237745685156851393567877,
    2466: 1213040219743698104212153283094735988868458164856735,
    2467: 1244272191922094708920237946746471334658921810675089,
    2468: 1276301817981140870474529866246359687648227775992726,
    2469: 1309149305865493979065272921268867078953610074980355,
    2470: 1342835371356799383941072744632607586619060990003342,
    2471: 1377381250733383747666895193431311551421473834674537,
    2472: 1412808713743003709421434478836269410607157240633931,
    2473: 1449140076896329138317020116671377802568526770518725,
    2474: 1486398217089027121199419785627770438512228407175000,
    2475: 1524606585560504203472825372845600976263733665501642,
    2476: 1563789222197560394205351099996482830581156974888244,
    2477: 1603970770191409168676519057930382172908445935119463,
    2478: 1645176491056723265830534175841536314124424257900655,
    2479: 1687432280021576600685684487181671811367617087501755,
    2480: 1730764681797368211260238937556940484156749101230455,
    2481: 1775200906738034957464112810216480762332001678674799,
    2482: 1820768847398085810011063048337611865735620543349686,
    2483: 1867497095499222138016227017428624557231848665351291,
    2484: 1915414959315545554866069359053268627009894091487255,
    2485: 1964552481487597746580633524928622127514294053468578,
    2486: 2014940457275725421793253569605575859047900517862975,
    2487: 2066610453263518227450300026070406061787487374956619,
    2488: 2119594826522328312496888837397949369108992226003579,
    2489: 2173926744248147339669532102906132397617461595649235,
    2490: 2229640203882390293040946390903966696602633829194840,
    2491: 2286770053728415559686499093247615980043870048333375,
    2492: 2345352014075897634933772608434944801289607520822444,
    2493: 2405422698845462573006497019894423614036351120521629,
    2494: 2467019637766297143181469675691820929552138013921170,
    2495: 2530181299099750724441152937967329319658147447405249,
    2496: 2594947112922264451615392923126900249342712365881980,
    2497: 2661357494981285189837685277991457183899724929972336,
    2498: 2729453871138152742649660700418835108908145695065284,
    2499: 2799278702412287477405614444445747930301938442180000,
    2500: 2870875510641352469269629800993561138276373608937244,
    2501: 2944288904772419516055596903431635682611440388817684,
    2502: 3019564607799532159016586951616642980389816614848623,
    2503: 3096749484363431362720513648966835225350796839944705,
    2504: 3175891569029590968434327113853291229809825601961265,
    2505: 3257040095261100652976951554528119114719453404725007,
    2506: 3340245525103334116822171147466786507458445890183988,
    2507: 3425559579597749814517587789768024144026745140376550,
    2508: 3513035269942590955686749126214187667970579050845937,
    2509: 3602726929418680979845445364711401806180203650663725,
    2510: 3694690246098950482357992748748848483474524052004611,
    2511: 3788982296360781887103496312666448565688651771156677,
    2512: 3885661579220719274616818998490729558629719751838590,
    2513: 3984788051511562939333648375836061468352863107532895,
    2514: 4086423163922351728879727101483809741806177963555690,
    2515: 4190629897922231281075551233411026977189480304097898,
    2516: 4297472803589713195797719954967455347047259565521535,
    2517: 4407018038369349240856665212333154882125704077589469,
    2518: 4519333406778376182071537408268876717047377660539309,
    2519: 4634488401086431042999613202320599056013666269808095,
    2520: 4752554242991993841520963249414089899868727306156151
}

def exp_sum(number):
    if number < 0: return 0
    return ANSWERS[number]

class Memoize:
    def __init__(self, func): 
        self.func = func
        self.cache = {}
    def __call__(self, arg):
        if arg not in self.cache: 
            self.cache[arg] = self.func(arg)
        return self.cache[arg]

@Memoize
def exp_sum(n):
    if n == 0: return 1
    result = 0; k = 1; sign = 1; 
    while True:
        pent = (3*k**2 - k) // 2        
        if pent > n: break
        result += sign * exp_sum(n - pent) 
        pent += k
        if pent > n: break
        result += sign * exp_sum(n - pent) 
        k += 1; sign = -sign; 
    return result

def exp_sum(n):
    if n < 0: return 0
    A = [1] + [0]*n
    for i in range(n):
        A = [sum(A[:k+1][::-i-1]) for k in range(n+1)]
    return A[-1]

def exp_sum(n,x=None, maxx=None,dic={}):
    x,maxx = (n,n) if x==None else (x,maxx)
    return sum([dic[(x-i,i)] if (x-i,i) in dic else(0 if dic.update({(x-i,i):exp_sum(n,x-i,i,dic)}) else dic[(x-i,i)])for i in range(1,min([maxx,x])+1)[::-1]]) if x else 1

dictionary = {}

def exp_sum(n, k=None):
    if k is None or k > n:
        k = n
    # use the usual recurrence relation, and memoization
    if n == 0 and k == 0:
        return 1
    elif n < 0 or k < 0:
        return 0
    else:
        if (n, k) in dictionary:
            return dictionary[(n, k)]
        else:
            sigma = 0
            for m in range(1, k + 1):
                sigma += exp_sum(n - m, m)
            dictionary[(n, k)] = sigma
            return sigma

import functools

@functools.lru_cache(1 << 16)
def f(n, m):
    if n == 0:
        return 1
    return sum(f(n - i, i) for i in range(1, min(n, m)+1))

def exp_sum(n):
    return f(n, n)

limit = 300
p = [1]+[0]*limit
for i in range(1,limit+1):
  for k,l in enumerate(range(i,limit+1)):
    p[l]+=p[k]
exp_sum=lambda n:p[n]