#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n)    fwd(i, 0, n)
#define all(X)       X.begin(), X.end()
#define sz(X)        int(size(X))
#define pb           push_back
#define eb           emplace_back
#define st           first
#define nd           second
using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) {
	*(int *)0 = 0;
});
#	define DTP(x, y)                                      \
		auto operator<<(auto &o, auto a)->decltype(y, o) { \
			o << "(";                                      \
			x;                                             \
			return o << ")";                               \
		}
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
void dump(auto... x) {
	((cerr << x << ", "), ...) << '\n';
}
#	define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x)
#else
#	define deb(...) 0
#endif

vi ways = {0,    0,    0,    2,    0,   0,    2,    3,    0,   7,    0,    5,
		   2,    3,    3,    8,    0,   5,    7,    8,    0,   17,   5,    9,
		   2,    6,    3,    21,   3,   9,    8,    12,   0,   26,   5,    15,
		   7,    12,   8,    23,   0,   14,   17,   17,   5,   31,   9,    18,
		   2,    24,   6,    32,   3,   18,   21,   23,   3,   41,   9,    23,
		   8,    21,   12,   58,   0,   18,   26,   26,   5,   47,   15,   27,
		   7,    26,   12,   44,   8,   44,   23,   30,   0,   62,   14,   32,
		   17,   26,   17,   53,   5,   32,   31,   42,   9,   62,   18,   38,
		   2,    35,   24,   86,   6,   36,   32,   39,   3,   83,   18,   41,
		   21,   39,   23,   68,   3,   41,   41,   45,   9,   82,   23,   56,
		   8,    55,   21,   77,   12,  42,   58,   48,   0,   86,   18,   50,
		   26,   71,   26,   99,   5,   50,   47,   53,   15,  92,   27,   62,
		   7,    48,   26,   122,  12,  54,   44,   57,   8,   110,  44,   60,
		   23,   57,   30,   98,   0,   84,   62,   62,   14,  122,  32,   63,
		   17,   60,   26,   137,  17,  63,   53,   81,   5,   116,  32,   68,
		   31,   66,   42,   113,  9,   63,   62,   83,   18,  180,  38,   72,
		   2,    71,   35,   116,  24,  72,   86,   75,   6,   131,  36,   96,
		   32,   71,   39,   160,  3,   104,  83,   80,   18,  137,  41,   83,
		   21,   111,  39,   137,  23,  77,   68,   84,   3,   157,  41,   86,
		   41,   84,   45,   221,  9,   86,   82,   90,   23,  152,  56,   90,
		   8,    89,   55,   184,  21,  120,  77,   101,  12,  161,  42,   95,
		   58,   122,  48,   155,  0,   95,   86,   123,  18,  184,  50,   99,
		   26,   93,   71,   167,  26,  99,   99,   102,  5,   218,  50,   119,
		   47,   102,  53,   211,  15,  104,  92,   107,  27,  197,  62,   137,
		   7,    106,  48,   182,  26,  108,  122,  113,  12,  263,  54,   120,
		   44,   152,  57,   188,  8,   108,  110,  116,  44,  197,  60,   117,
		   23,   116,  57,   286,  30,  117,  98,   140,  0,   206,  84,   134,
		   62,   111,  62,   203,  14,  165,  122,  125,  32,  235,  63,   128,
		   17,   125,  60,   212,  26,  161,  137,  171,  17,  233,  63,   131,
		   53,   129,  81,   258,  5,   131,  116,  135,  32,  287,  68,   135,
		   31,   151,  66,   275,  42,  131,  113,  138,  9,   263,  63,   177,
		   62,   138,  83,   230,  18,  135,  180,  143,  38,  242,  72,   144,
		   2,    218,  71,   290,  35,  144,  116,  158,  24,  251,  72,   150,
		   86,   147,  75,   356,  6,   149,  131,  159,  36,  302,  96,   179,
		   32,   152,  71,   257,  39,  206,  160,  158,  3,   266,  104,  158,
		   83,   156,  80,   313,  18,  149,  137,  204,  41,  317,  83,   162,
		   21,   161,  111,  266,  39,  197,  137,  165,  23,  415,  77,   167,
		   68,   161,  84,   278,  3,   167,  157,  200,  41,  287,  86,   213,
		   41,   170,  84,   341,  45,  171,  221,  174,  9,   308,  86,   176,
		   82,   233,  90,   293,  23,  221,  152,  194,  56,  337,  90,   180,
		   8,    174,  89,   422,  55,  176,  184,  183,  21,  311,  120,  185,
		   77,   179,  101,  416,  12,  246,  161,  188,  42,  317,  95,   189,
		   58,   183,  122,  314,  48,  189,  155,  245,  0,   422,  95,   195,
		   86,   239,  123,  323,  18,  194,  184,  197,  50,  419,  99,   209,
		   26,   216,  93,   392,  71,  194,  167,  203,  26,  341,  99,   317,
		   99,   201,  102,  338,  5,   198,  218,  206,  50,  388,  119,  227,
		   47,   273,  102,  341,  53,  207,  211,  218,  15,  419,  104,  212,
		   92,   206,  107,  545,  27,  212,  197,  215,  62,  362,  137,  231,
		   7,    215,  106,  362,  48,  287,  182,  257,  26,  409,  108,  221,
		   122,  260,  113,  368,  12,  221,  263,  281,  54,  377,  120,  225,
		   44,   224,  152,  443,  57,  271,  188,  228,  8,   488,  108,  237,
		   110,  228,  116,  380,  44,  230,  197,  233,  60,  498,  117,  299,
		   23,   228,  116,  518,  57,  230,  286,  237,  30,  401,  117,  240,
		   98,   315,  140,  466,  0,   239,  206,  242,  84,  422,  134,  243,
		   62,   299,  111,  557,  62,  243,  203,  248,  14,  467,  165,  248,
		   122,  246,  125,  410,  32,  353,  235,  270,  63,  422,  128,  296,
		   17,   251,  125,  495,  60,  252,  212,  326,  26,  431,  161,  257,
		   137,  251,  171,  428,  17,  252,  233,  260,  63,  749,  131,  263,
		   53,   257,  129,  437,  81,  261,  258,  290,  5,   458,  131,  339,
		   116,  264,  135,  517,  32,  309,  287,  311,  68,  452,  135,  270,
		   31,   354,  151,  452,  66,  261,  275,  273,  42,  549,  131,  287,
		   113,  273,  138,  608,  9,   338,  263,  278,  63,  512,  177,  279,
		   62,   273,  138,  545,  83,  368,  230,  282,  18,  476,  135,  285,
		   180,  282,  143,  611,  38,  284,  242,  366,  72,  539,  144,  296,
		   2,    287,  218,  482,  71,  288,  290,  306,  35,  623,  144,  323,
		   116,  356,  158,  576,  24,  288,  251,  296,  72,  497,  150,  380,
		   86,   291,  147,  491,  75,  297,  356,  311,  6,   569,  149,  356,
		   131,  420,  159,  503,  36,  302,  302,  305,  96,  512,  179,  308,
		   32,   356,  152,  745,  71,  306,  257,  309,  39,  608,  206,  311,
		   160,  309,  158,  518,  3,   413,  266,  315,  104, 657,  158,  315,
		   83,   312,  156,  527,  80,  306,  313,  490,  18,  536,  149,  345,
		   137,  318,  204,  671,  41,  320,  317,  323,  83,  692,  162,  324,
		   21,   318,  161,  542,  111, 395,  266,  335,  39,  620,  197,  417,
		   137,  327,  165,  548,  23,  329,  415,  332,  77,  572,  167,  333,
		   68,   435,  161,  791,  84,  386,  278,  338,  3,   608,  167,  357,
		   157,  332,  200,  761,  41,  333,  287,  341,  86,  643,  213,  342,
		   41,   416,  170,  566,  84,  449,  341,  345,  45,  581,  171,  354,
		   221,  336,  174,  670,  9,   347,  308,  512,  86,  587,  176,  410,
		   82,   350,  233,  587,  90,  351,  293,  383,  23,  894,  221,  356,
		   152,  350,  194,  593,  56,  356,  337,  360,  90,  707,  180,  461,
		   8,    384,  174,  698,  89,  356,  422,  363,  55,  674,  176,  365,
		   184,  476,  183,  599,  21,  365,  311,  434,  120, 694,  185,  369,
		   77,   363,  179,  827,  101, 422,  416,  372,  12,  626,  246,  375,
		   161,  372,  188,  735,  42,  569,  317,  389,  95,  647,  189,  416,
		   58,   377,  183,  632,  122, 378,  314,  483,  48,  722,  189,  383,
		   155,  381,  245,  806,  0,   374,  422,  393,  95,  857,  195,  387,
		   86,   386,  239,  796,  123, 383,  323,  390,  18,  656,  194,  501,
		   184,  512,  197,  653,  50,  392,  419,  395,  99,  785,  209,  398,
		   26,   516,  216,  662,  93,  396,  392,  399,  71,  683,  194,  473,
		   167,  399,  203,  977,  26,  396,  341,  419,  99,  677,  317,  413,
		   99,   459,  201,  755,  102, 555,  338,  408,  5,   930,  198,  410,
		   218,  408,  206,  680,  50,  410,  388,  528,  119, 692,  227,  414,
		   47,   395,  273,  818,  102, 414,  341,  491,  53,  893,  207,  420,
		   211,  417,  218,  698,  15,  482,  419,  422,  104, 793,  212,  609,
		   92,   422,  206,  701,  107, 512,  545,  428,  27,  716,  212,  440,
		   197,  557,  215,  823,  62,  423,  362,  456,  137, 722,  231,  432,
		   7,    431,  215,  1097, 106, 428,  362,  479,  48,  899,  287,  437,
		   182,  431,  257,  728,  26,  570,  409,  440,  108, 797,  221,  456,
		   122,  533,  260,  851,  113, 441,  368,  567,  12,  758,  221,  446,
		   263,  440,  281,  743,  54,  446,  377,  450,  120, 1208, 225,  530,
		   44,   449,  224,  752,  152, 446,  443,  464,  57,  803,  271,  582,
		   188,  453,  228,  910,  8,   455,  488,  495,  108, 902,  237,  459,
		   110,  606,  228,  767,  116, 459,  380,  462,  44,  875,  230,  506,
		   197,  462,  233,  1031, 60,  461,  498,  551,  117, 797,  299,  488,
		   23,   467,  228,  902,  116, 611,  518,  473,  57,  791,  230,  473,
		   286,  467,  237,  788,  30,  608,  401,  609,  117, 975,  240,  506,
		   98,   545,  315,  788,  140, 477,  466,  480,  0,   1028, 239,  482,
		   206,  476,  242,  1079, 84,  482,  422,  485,  134, 812,  243,  618,
		   62,   485,  299,  812,  111, 486,  557,  489,  62,  919,  243,  491,
		   203,  746,  248,  986,  14,  486,  467,  495,  165, 827,  248,  495,
		   122,  494,  246,  1293, 125, 486,  410,  498,  32,  836,  353,  600,
		   235,  557,  270,  830,  63,  651,  422,  510,  128, 949,  296,  515,
		   17,   498,  251,  842,  125, 575,  495,  650,  60,  1004, 252,  510,
		   212,  572,  326,  976,  26,  509,  431,  531,  161, 1091, 257,  513,
		   137,  510,  251,  857,  171, 513,  428,  605,  17,  1031, 252,  663,
		   233,  516,  260,  863,  63,  513,  749,  575,  131, 872,  263,  530,
		   53,   678,  257,  1051, 129, 629,  437,  525,  81,  881,  261,  570,
		   258,  521,  290,  1166, 5,   527,  458,  542,  131, 1000, 339,  533,
		   116,  525,  264,  1103, 135, 705,  517,  534,  32,  983,  309,  536,
		   287,  534,  311,  1053, 68,  536,  452,  686,  135, 902,  270,  540,
		   31,   650,  354,  896,  151, 532,  452,  543,  66,  1435, 261,  545,
		   275,  543,  273,  905,  42,  606,  549,  548,  131, 917,  287,  923,
		   113,  543,  273,  1055, 138, 545,  608,  552,  9,   926,  338,  569,
		   263,  719,  278,  920,  63,  554,  512,  557,  177, 1295, 279,  558,
		   62,   557,  273,  1232, 138, 558,  545,  603,  83,  941,  368,  563,
		   230,  638,  282,  1078, 18,  758,  476,  668,  135, 947,  285,  567,
		   180,  563,  282,  941,  143, 563,  611,  804,  38,  1075, 284,  572,
		   242,  561,  366,  953,  72,  689,  539,  575,  144, 1232, 296,  578,
		   2,    570,  287,  1274, 218, 647,  482,  579,  71,  983,  288,  740,
		   290,  579,  306,  1196, 35,  581,  623,  585,  144, 1102, 323,  585,
		   116,  759,  356,  977,  158, 581,  576,  588,  24,  986,  288,  590,
		   251,  706,  296,  1432, 72,  671,  497,  593,  150, 1052, 380,  594,
		   86,   588,  291,  1082, 147, 773,  491,  623,  75,  1217, 297,  701,
		   356,  597,  311,  995,  6,   599,  569,  771,  149, 1022, 356,  603,
		   131,  602,  420,  1157, 159, 603,  503,  665,  36,  1586, 302,  608,
		   302,  606,  305,  1013, 96,  594,  512,  611,  179, 1153, 308,  785,
		   32,   684,  356,  1016, 152, 612,  745,  725,  71,  1031, 306,  654,
		   257,  825,  309,  1212, 39,  614,  608,  627,  206, 1142, 311,  623,
		   160,  620,  309,  1367, 158, 746,  518,  624,  3,   1174, 413,  626,
		   266,  624,  315,  1043, 104, 813,  657,  644,  158, 1097, 315,  683,
		   83,   628,  312,  1418, 156, 626,  527,  812,  80,  1061, 306,  701,
		   313,  633,  490,  1055, 18,  635,  536,  638,  149, 1639, 345,  647,
		   137,  803,  318,  1067, 204, 639,  671,  662,  41,  1076, 320,  855,
		   317,  638,  323,  1231, 83,  644,  692,  647,  162, 1169, 324,  764,
		   21,   920,  318,  1082, 161, 648,  542,  653,  111, 1232, 395,  678,
		   266,  651,  335,  1436, 39,  648,  620,  656,  197, 1292, 417,  668,
		   137,  656,  327,  1287, 165, 854,  548,  660,  23,  1106, 329,  692,
		   415,  656,  332,  1301, 77,  657,  572,  1097, 167, 1255, 333,  681,
		   68,   665,  435,  1112, 161, 662,  791,  669,  84,  1430, 386,  671,
		   278,  669,  338,  1282, 3,   806,  608,  675,  167, 1127, 357,  866,
		   157,  674,  332,  1127, 200, 751,  761,  686,  41,  1376, 333,  680,
		   287,  900,  341,  1361, 86,  759,  643,  695,  213, 1142, 342,  684,
		   41,   674,  416,  1663, 170, 755,  566,  687,  84,  1193, 449,  690,
		   341,  824,  345,  1148, 45,  894,  581,  764,  171, 1304, 354,  693,
		   221,  727,  336,  1157, 174, 689,  670,  888,  9,   1166, 347,  821,
		   308,  696,  512,  1511, 86,  693,  587,  701,  176, 1502, 410,  702,
		   82,   701,  350,  1166, 233, 702,  587,  705,  90,  1751, 351,  906,
		   293,  687,  383,  1175, 23,  707,  894,  753,  221, 1187, 356,  713,
		   152,  921,  350,  1361, 194, 711,  593,  842,  56,  1208, 356,  716,
		   337,  797,  360,  1583, 90,  716,  707,  720,  180, 1452, 461,  794,
		   8,    716,  384,  1202, 174, 1094, 698,  752,  89,  1211, 356,  725,
		   422,  723,  363,  1436, 55,  720,  674,  933,  176, 1217, 365,  749,
		   184,  723,  476,  1493, 183, 729,  599,  732,  21,  1894, 365,  791,
		   311,  827,  434,  1223, 120, 729,  694,  744,  185, 1247, 369,  947,
		   77,   884,  363,  1454, 179, 738,  827,  756,  101, 1241, 422,  743,
		   416,  962,  372,  1238, 12,  738,  626,  746,  246, 1406, 375,  881,
		   161,  746,  372,  1772, 188, 747,  735,  750,  42,  1358, 569,  752,
		   317,  746,  389,  1435, 95,  998,  647,  755,  189, 1487, 416,  798,
		   58,   755,  377,  1262, 183, 827,  632,  973,  122, 1508, 378,  761,
		   314,  759,  483,  1268, 48,  860,  722,  896,  189, 1637, 383,  765,
		   155,  759,  381,  1463, 245, 761,  806,  833,  0,   1286, 374,  987,
		   422,  768,  393,  1280, 95,  926,  857,  792,  195, 1459, 387,  774,
		   86,   1028, 386,  1286, 239, 774,  796,  857,  123, 1301, 383,  794,
		   323,  854,  390,  2330, 18,  779,  656,  782,  194, 1322, 501,  783,
		   184,  782,  512,  1307, 197, 1095, 653,  788,  50,  1487, 392,  788,
		   419,  941,  395,  1313, 99,  783,  785,  1097, 209, 1457, 398,  792,
		   26,   791,  516,  1561, 216, 788,  662,  803,  93,  1703, 396,  941,
		   392,  782,  399,  1328, 71,  797,  683,  800,  194, 1611, 473,  1023,
		   167,  800,  399,  1547, 203, 801,  977,  804,  26,  1580, 396,  890,
		   341,  1043, 419,  1537, 99,  806,  677,  810,  317, 1352, 413,  821,
		   99,   809,  459,  1772, 201, 806,  755,  959,  102, 1538, 555,  822,
		   338,  809,  408,  1349, 5,   1056, 930,  818,  198, 1367, 410,  845,
		   218,  983,  408,  1643, 206, 980,  680,  1055, 50,  1439, 410,  825,
		   388,  819,  528,  1373, 119, 903,  692,  827,  227, 2071, 414,  828,
		   47,   864,  395,  1688, 273, 828,  818,  833,  102, 1391, 414,  1068,
		   341,  831,  491,  1742, 53,  824,  893,  848,  207, 1397, 420,  908,
		   211,  1271, 417,  1391, 218, 837,  698,  840,  15,  1694, 482,  842,
		   419,  836,  422,  1841, 104, 837,  793,  845,  212, 1412, 609,  995,
		   92,   840,  422,  1616, 206, 1205, 701,  902,  107, 1433, 512,  851,
		   545,  849,  428,  1418, 27,  851,  716,  1086, 212, 2075, 440,  893,
		   197,  854,  557,  1427, 215, 851,  823,  858,  62,  1838, 423,  879,
		   362,  858,  456,  1688, 137, 860,  722,  1145, 231, 1487, 432,  1194,
		   7,    858,  431,  1442, 215, 864,  1097, 867,  106, 1640, 428,  870,
		   362,  1124, 479,  1448, 48,  1040, 899,  945,  287, 1544, 437,  881,
		   182,  869,  431,  2122, 257, 873,  728,  878,  26,  1619, 570,  878,
		   409,  876,  440,  1781, 108, 1163, 797,  881,  221, 1751, 456,  882,
		   122,  876,  533,  1466, 260, 882,  851,  1136, 113, 1481, 441,  899,
		   368,  1097, 567,  1690, 12,  984,  758,  890,  221, 1907, 446,  980,
		   263,  890,  440,  1481, 281, 891,  743,  894,  54,  1684, 446,  1448,
		   377,  894,  450,  1493, 120, 896,  1208, 900,  225, 1562, 530,  900,
		   44,   1200, 449,  1772, 224, 882,  752,  923,  152, 1784, 446,  905,
		   443,  1016, 464,  2108, 57,  905,  803,  938,  271, 1714, 582,  909,
		   188,  899,  453,  1517, 228, 1178, 910,  1073, 8,   1526, 455,  915,
		   488,  912,  495,  1741, 108, 914,  902,  1176, 237, 1547, 459,  918,
		   110,  1002, 606,  1778, 228, 1097, 767,  923,  116, 2325, 459,  923,
		   380,  1022, 462,  1538, 44,  905,  875,  926,  230, 1547, 506,  1190,
		   197,  926,  462,  2072, 233, 927,  1031, 956,  60,  1556, 461,  939,
		   498,  1230, 551,  1553, 117, 1049, 797,  972,  299, 1765, 488,  938,
		   23,   1118, 467,  2072, 228, 932,  902,  939,  116, 1583, 611,  1020,
		   518,  935,  473,  1994, 57,  1218, 791,  945,  230, 1577, 473,  1115,
		   286,  944,  467,  1574, 237, 936,  788,  1354, 30,  1793, 608,  950,
		   401,  944,  609,  1574, 117, 1031, 975,  953,  240, 2450, 506,  954,
		   98,   948,  545,  1820, 315, 954,  788,  957,  140, 1733, 477,  1226,
		   466,  957,  480,  1598, 0,   954,  1028, 1136, 239, 2090, 482,  974,
		   206,  1245, 476,  1607, 242, 1052, 1079, 981,  84,  1616, 482,  968,
		   422,  962,  485,  2354, 134, 1193, 812,  978,  243, 1622, 618,  972,
		   62,   971,  485,  1616, 299, 1290, 812,  1058, 111, 1845, 486,  1079,
		   557,  971,  489,  1976, 62,  977,  919,  1257, 243, 1682, 491,  983,
		   203,  980,  746,  1931, 248, 981,  986,  1028, 14,  2105, 486,  1011,
		   467,  1175, 495,  1643, 165, 986,  827,  1046, 248, 1867, 495,  1266,
		   122,  1112, 494,  1652, 246, 1080, 1293, 993,  125, 1661, 486,  1175,
		   410,  1286, 498,  1946, 32,  995,  836,  998,  353, 1667, 600,  999,
		   235,  980,  557,  2177, 270, 995,  830,  1002, 63,  2372, 651,  1019,
		   422,  1002, 510,  1931, 128, 1299, 949,  1007, 296, 1697, 515,  1008,
		   17,   1007, 498,  2071, 251, 1008, 842,  1583, 125, 1793, 575,  1013,
		   495,  1007, 650,  1685, 60,  1008, 1004, 1016, 252, 2585, 510,  1017,
		   212,  1016, 572,  1691, 326, 1331, 976,  1020, 26,  1706, 509,  1311,
		   431,  1011, 531,  2007, 161, 1022, 1091, 1025, 257, 1712, 513,  1028,
		   137,  1433, 510,  2078, 251, 1026, 857,  1037, 171, 1939, 513,  1061,
		   428,  1029, 605,  2246, 17,  1031, 1031, 1136, 252, 1727, 663,  1100,
		   233,  1235, 516,  1973, 260, 1365, 863,  1038, 63,  1778, 513,  1052,
		   749,  1121, 575,  1724, 131, 1040, 872,  1338, 263, 2088, 530,  1360,
		   53,   1038, 678,  1742, 257, 1044, 1051, 1047, 129, 2561, 629,  1091,
		   437,  1047, 525,  1996, 81,  1049, 881,  1052, 261, 2072, 570,  1352,
		   258,  1050, 521,  1757, 290, 1049, 1166, 1058, 5,   1997, 527,  1058,
		   458,  1446, 542,  1763, 131, 1049, 1000, 1253, 339, 1922, 533,  1172,
		   116,  1061, 525,  2717, 264, 1062, 1103, 1076, 135, 1781, 705,  1067,
		   517,  1061, 534,  1775, 32,  1622, 983,  1070, 309, 2020, 536,  1073,
		   287,  1070, 534,  1787, 311, 1071, 1053, 1379, 68,  1808, 536,  1119,
		   452,  1205, 686,  2405, 135, 1067, 902,  1167, 270, 2312, 540,  1080,
		   31,   1166, 650,  1922, 354, 1076, 896,  1083, 151, 2171, 532,  1487,
		   452,  1292, 543,  1805, 66,  1085, 1435, 1095, 261, 1817, 545,  1089,
		   275,  1433, 543,  2285, 273, 1089, 905,  1121, 42,  1826, 606,  1286,
		   549,  1092, 548,  2381, 131, 1209, 917,  1122, 287, 2062, 923,  1098,
		   113,  1092, 543,  1832, 273, 1421, 1055, 1103, 138, 2174, 545,  1103,
		   608,  1097, 552,  2166, 9,   1298, 926,  1419, 338, 1847, 569,  1115,
		   263,  1106, 719,  1841, 278, 1107, 920,  1310, 63,  2812, 554,  1112,
		   512,  1106, 557,  2111, 177, 1112, 1295, 1115, 279, 1862, 558,  1424,
		   62,   1110, 557,  2126, 273, 1331, 1232, 1235, 138, 1883, 558,  1140,
		   545,  1485, 603,  1868, 83,  1118, 941,  1125, 368, 2234, 563,  1125,
		   230,  1124, 638,  2852, 282, 1121, 1078, 1199, 18,  1949, 758,  1130,
		   476,  1247, 668,  2201, 135, 1461, 947,  1133, 285, 2087, 567,  1134,
		   180,  1357, 563,  1892, 282, 1130, 941,  1460, 143, 2150, 563,  1140,
		   611,  1137, 804,  1898, 38,  1139, 1075, 1154, 284, 2441, 572,  1349,
		   242,  1142, 561,  2249, 366, 1232, 953,  1188, 72,  1916, 689,  1772,
		   539,  1146, 575,  1913, 144, 1143, 1232, 1151, 296, 2738, 578,  1178,
		   2,    1488, 570,  1913, 287, 1148, 1274, 1155, 218, 1973, 647,  1157,
		   482,  1151, 579,  2914, 71,  1157, 983,  1370, 288, 1937, 740,  1163,
		   290,  1301, 579,  1937, 306, 1502, 1196, 1184, 35,  2484, 581,  1173,
		   623,  1164, 585,  1940, 144, 1391, 1102, 1496, 323, 1952, 585,  1170,
		   116,  1169, 759,  2228, 356, 1164, 977,  1211, 158, 2513, 581,  1248,
		   576,  1169, 588,  2564, 24,  1175, 986,  1232, 288, 2224, 590,  1514,
		   251,  1160, 706,  1967, 296, 1268, 1432, 1283, 72,  1976, 671,  1185,
		   497,  1799, 593,  2365, 150, 1179, 1052, 1187, 380, 1997, 594,  1188,
		   86,   1187, 588,  2582, 291, 1331, 1082, 1206, 147, 2252, 773,  1409,
		   491,  1191, 623,  1988, 75,  1578, 1217, 1196, 297, 1997, 701,  1197,
		   356,  1299, 597,  2326, 311, 1322, 995,  1541, 6,   2369, 599,  1202,
		   569,  1196, 771,  2003, 149, 1202, 1022, 1328, 356, 3044, 603,  1208,
		   131,  1205, 602,  2006, 420, 1206, 1157, 1427, 159, 2108, 603,  1554,
		   503,  1209, 665,  2302, 36,  1206, 1586, 1215, 302, 2072, 608,  1244,
		   302,  1569, 606,  2297, 305, 1487, 1013, 1229, 96,  2562, 594,  1220,
		   512,  1218, 611,  2783, 179, 1220, 1153, 1223, 308, 2042, 785,  1232,
		   32,   1218, 684,  2890, 356, 1583, 1016, 1227, 152, 2051, 612,  1244,
		   745,  1223, 725,  2048, 71,  1226, 1031, 1682, 306, 2324, 654,  1361,
		   257,  1583, 825,  2057, 309, 1229, 1212, 1238, 39,  2648, 614,  1238,
		   608,  1236, 627,  2353, 206, 1233, 1142, 1241, 311, 2072, 623,  1976,
		   160,  1241, 620,  2054, 309, 1349, 1367, 1245, 158, 2480, 746,  1247,
		   518,  1769, 624,  2078, 3,   1247, 1174, 1250, 413, 2462, 626,  1353,
		   266,  1341, 624,  3040, 315, 1247, 1043, 1254, 104, 2108, 813,  1256,
		   657,  1250, 644,  2093, 158, 1623, 1097, 1481, 315, 2377, 683,  1260,
		   83,   1259, 628,  2408, 312, 1256, 1418, 1617, 156, 2111, 626,  1265,
		   527,  1263, 812,  2481, 80,  1508, 1061, 1347, 306, 3047, 701,  1280,
		   313,  1263, 633,  2117, 490, 1269, 1055, 1272, 18,  2398, 635,  1631,
		   536,  1367, 638,  2561, 149, 1427, 1639, 1307, 345, 2147, 647,  1278,
		   137,  1650, 803,  2432, 318, 1278, 1067, 1283, 204, 2204, 639,  1290,
		   671,  1526, 662,  2786, 41,  1274, 1076, 1395, 320, 2565, 855,  1340,
		   317,  1286, 638,  2141, 323, 1664, 1231, 1424, 83,  2288, 644,  1526,
		   692,  1272, 647,  2455, 162, 1292, 1169, 1658, 324, 2162, 764,  1298,
		   21,   1295, 920,  2162, 318, 1296, 1082, 1299, 161, 3731, 648,  1301,
		   542,  1299, 653,  2165, 111, 1434, 1232, 1319, 395, 2402, 678,  1779,
		   266,  1351, 651,  2723, 335, 1289, 1436, 1544, 39,  2186, 648,  1310,
		   620,  1691, 656,  2180, 197, 1305, 1292, 1313, 417, 2479, 668,  1397,
		   137,  1308, 656,  2852, 327, 1576, 1287, 1317, 165, 2201, 854,  1451,
		   548,  1317, 660,  2711, 23,  1704, 1106, 1329, 329, 2294, 692,  1323,
		   415,  1322, 656,  2663, 332, 1323, 1301, 1698, 77,  2648, 657,  1328,
		   572,  1326, 1097, 2213, 167, 1323, 1255, 1331, 333, 2849, 681,  1370,
		   68,   1745, 665,  2581, 435, 1332, 1112, 1335, 161, 2231, 662,  1716,
		   791,  1545, 669,  2225, 84,  1436, 1430, 1340, 386, 2530, 671,  1574,
		   278,  1778, 669,  2237, 338, 1341, 1282, 1344, 3,   2258, 806,  1358,
		   608,  1340, 675,  3761, 167, 1346, 1127, 1350, 357, 2657, 866,  1394,
		   157,  1344, 674,  2252, 332, 1770, 1127, 1353, 200, 2558, 751,  1470,
		   761,  1353, 686,  2255, 41,  1355, 1376, 2150, 333, 2327, 680,  1359,
		   287,  1344, 900,  2734, 341, 1520, 1361, 1362, 86,  2918, 759,  1365,
		   643,  1362, 695,  2273, 213, 1625, 1142, 1367, 342, 2733, 684,  1757,
		   41,   1364, 674,  2282, 416, 1364, 1663, 1430, 170, 2483, 755,  1373,
		   566,  1772, 687,  3068, 84,  1368, 1193, 1520, 449, 2297, 690,  1377,
		   341,  1376, 824,  3044, 345, 1377, 1148, 1388, 45,  2609, 894,  1401,
		   581,  1682, 764,  2303, 171, 1892, 1304, 1385, 354, 2312, 693,  1388,
		   221,  1385, 727,  2726, 336, 1386, 1157, 1947, 174, 2555, 689,  1643,
		   670,  1389, 888,  2318, 9,   1488, 1166, 1395, 347, 3503, 821,  1395,
		   308,  1392, 696,  2327, 512, 1386, 1511, 1398, 86,  2759, 693,  1793,
		   587,  1398, 701,  2711, 176, 1395, 1502, 1403, 410, 2447, 702,  1550,
		   82,   1838, 701,  2342, 350, 1547, 1166, 1795, 233, 2807, 702,  1410,
		   587,  1399, 705,  3056, 90,  1409, 1751, 1449, 351, 2372, 906,  1413,
		   293,  1412, 687,  2687, 383, 2228, 1175, 1431, 23,  2366, 707,  1418,
		   894,  1583, 753,  2360, 221, 1413, 1187, 1824, 356, 2683, 713,  1433,
		   152,  1421, 921,  3047, 350, 1422, 1361, 1445, 194, 3053, 711,  1427,
		   593,  1421, 842,  2960, 56,  1422, 1208, 1455, 356, 2537, 716,  1833,
		   337,  1703, 797,  2723, 360, 1431, 1583, 1434, 90,  2702, 716,  1502,
		   707,  1853, 720,  2393, 180, 1436, 1452, 1481, 461, 2402, 794,  1700,
		   8,    1584, 716,  3499, 384, 1436, 1202, 1443, 174, 2411, 1094, 1445,
		   698,  1443, 752,  2405, 89,  2054, 1211, 1460, 356, 3362, 725,  1449,
		   422,  1443, 723,  2417, 363, 1445, 1436, 1974, 55,  2426, 720,  1542,
		   674,  1452, 933,  2761, 176, 1454, 1217, 1721, 365, 3116, 749,  1581,
		   184,  1457, 723,  2432, 476, 1454, 1493, 1610, 183, 2762, 729,  1878,
		   599,  1562, 732,  2438, 21,  1778, 1894, 1466, 365, 2447, 791,  1467,
		   311,  1973, 827,  2877, 434, 1467, 1223, 1470, 120, 2456, 729,  1472,
		   694,  1461, 744,  3734, 185, 1472, 1247, 1475, 369, 3350, 947,  1478,
		   77,   1596, 884,  2456, 363, 1907, 1454, 1479, 179, 2483, 738,  1481,
		   827,  1760, 756,  2812, 101, 1580, 1241, 1901, 422, 2477, 743,  1511,
		   416,  1481, 962,  2477, 372, 1467, 1238, 1488, 12,  3926, 738,  1958,
		   626,  1484, 746,  2474, 246, 1487, 1406, 1620, 375, 2492, 881,  1919,
		   161,  1488, 746,  2840, 372, 1494, 1772, 1505, 188, 2999, 747,  1556,
		   735,  1934, 750,  2786, 42,  1499, 1358, 1502, 569, 2834, 752,  1503,
		   317,  1679, 746,  3257, 389, 1503, 1435, 1775, 95,  2558, 998,  1508,
		   647,  1506, 755,  2961, 189, 2106, 1487, 1511, 416, 2582, 798,  1532,
		   58,   1506, 755,  2516, 377, 1799, 1262, 1946, 183, 2864, 827,  1524,
		   632,  1511, 973,  2876, 122, 1517, 1508, 1520, 378, 3257, 761,  1523,
		   314,  1520, 759,  3407, 483, 1646, 1268, 1535, 48,  2558, 860,  2072,
		   722,  1520, 896,  2861, 189, 1526, 1637, 1544, 383, 3042, 765,  1530,
		   155,  2324, 759,  2552, 381, 1772, 1463, 1577, 245, 2663, 761,  1535,
		   806,  1533, 833,  3724, 0,   1532, 1286, 1538, 374, 2567, 987,  1817,
		   422,  1533, 768,  2564, 393, 1988, 1280, 1542, 95,  2915, 926,  1545,
		   857,  1697, 792,  2573, 195, 1539, 1459, 2339, 387, 3044, 774,  1548,
		   86,   1547, 1028, 3098, 386, 1548, 1286, 1553, 239, 3323, 774,  1553,
		   796,  1547, 857,  2588, 123, 1548, 1301, 1832, 383, 2938, 794,  2000,
		   323,  1556, 854,  2591, 390, 1557, 2330, 1560, 18,  2879, 779,  1695,
		   656,  2066, 782,  2965, 194, 1859, 1322, 1637, 501, 2657, 783,  1581,
		   184,  1565, 782,  3392, 512, 1562, 1307, 1634, 197, 3279, 1095, 1608,
		   653,  1670, 788,  3146, 50,  2028, 1487, 1575, 392, 2627, 788,  1736,
		   419,  1574, 941,  2993, 395, 1566, 1313, 2027, 99,  2858, 783,  1580,
		   785,  1877, 1097, 2630, 209, 1580, 1457, 1583, 398, 3962, 792,  1613,
		   26,   1566, 791,  2642, 516, 1584, 1561, 1587, 216, 2714, 788,  2446,
		   662,  1772, 803,  3120, 93,  1589, 1703, 1592, 396, 2672, 941,  1694,
		   392,  2055, 782,  2651, 399, 1593, 1328, 1728, 71,  3740, 797,  1598,
		   683,  1596, 800,  3533, 194, 1593, 1611, 1613, 473, 2672, 1023, 1602,
		   167,  1601, 800,  3347, 399, 2148, 1547, 1895, 203, 2681, 801,  1607,
		   977,  1601, 804,  2678, 26,  1607, 1580, 2067, 396, 3200, 890,  1613,
		   341,  1610, 1043, 2687, 419, 2072, 1537, 1622, 99,  3455, 806,  1670,
		   677,  1745, 810,  3067, 317, 1805, 1352, 1620, 413, 2702, 821,  2081,
		   99,   1614, 809,  3248, 459, 1611, 1772, 1623, 201, 3061, 806,  1668,
		   755,  2096, 959,  2702, 102, 1625, 1538, 1628, 555, 2717, 822,  1703,
		   338,  1973, 809,  4473, 408, 1629, 1349, 1802, 5,   2726, 1056, 1676,
		   930,  1632, 818,  2723, 198, 2168, 1367, 1637, 410, 3089, 845,  1934,
		   218,  1634, 983,  3032, 408, 1638, 1643, 2103, 206, 2741, 980,  1662,
		   680,  1637, 1055, 3118, 50,  1638, 1439, 1676, 410, 4613, 825,  1647,
		   388,  1809, 819,  2741, 528, 1647, 1373, 1688, 119, 3284, 903,  2117,
		   692,  1646, 827,  2750, 227, 1652, 2071, 1955, 414, 2762, 828,  1658,
		   47,   2136, 864,  3146, 395, 1656, 1688, 1659, 273, 2858, 828,  1835,
		   818,  1772, 833,  3596, 102, 2090, 1391, 1665, 414, 3140, 1068, 1808,
		   341,  1664, 831,  2777, 491, 2175, 1742, 1668, 53,  2786, 824,  1670,
		   893,  1664, 848,  3929, 207, 1670, 1397, 2226, 420, 2792, 908,  1674,
		   211,  1928, 1271, 2792, 417, 1670, 1391, 1688, 218, 4189, 837,  1694,
		   698,  2011, 840,  2798, 15,  1679, 1694, 1682, 482, 3041, 842,  2162,
		   419,  1735, 836,  3197, 422, 1683, 1841, 1788, 104, 2816, 837,  1994,
		   793,  2177, 845,  3191, 212, 1670, 1412, 1691, 609, 3360, 995,  1700,
		   92,   1691, 840,  3797, 422, 1692, 1616, 1695, 206, 3344, 1205, 1697,
		   701,  1686, 902,  3220, 107, 2190, 1433, 1845, 512, 2837, 851,  1703,
		   545,  1695, 849,  2837, 428, 1898, 1418, 2678, 27,  3214, 851,  1706,
		   716,  1704, 1086, 2840, 212, 1701, 2075, 1710, 440, 4022, 893,  1781,
		   197,  1709, 854,  3357, 557, 2072, 1427, 1713, 215, 2861, 851,  2202,
		   823,  1709, 858,  2849, 62,  1884, 1838, 1898, 423, 3244, 879,  1719,
		   362,  2243, 858,  3443, 456, 1715, 1688, 1722, 137, 2876, 860,  1725,
		   722,  1722, 1145, 4190, 231, 1841, 1487, 1727, 432, 2897, 1194, 1739,
		   7,    2054, 858,  2876, 431, 2231, 1442, 1773, 215, 3827, 864,  1842,
		   1097, 1731, 867,  3236, 106, 1719, 1640, 2229, 428, 2897, 870,  2051,
		   362,  1733, 1124, 3346, 479, 1737, 1448, 1740, 48,  3725, 1040, 1742,
		   899,  1736, 945,  2903, 287, 1742, 1544, 1745, 437, 4064, 881,  2558,
		   182,  1745, 869,  2912, 431, 1853, 2122, 1749, 257, 2933, 873,  1758,
		   728,  2445, 878,  3438, 26,  1751, 1619, 2063, 570, 2927, 878,  1755,
		   409,  1893, 876,  3797, 440, 1751, 1781, 1838, 108, 3323, 1163, 1760,
		   797,  1954, 881,  2930, 221, 2675, 1751, 1788, 456, 2942, 882,  1764,
		   122,  1758, 876,  3350, 533, 1760, 1466, 2270, 260, 2951, 882,  1916,
		   851,  1763, 1136, 3536, 113, 1769, 1481, 1772, 441, 4470, 899,  1793,
		   368,  1772, 1097, 3353, 567, 1773, 1690, 1778, 12,  2966, 984,  2283,
		   758,  2111, 890,  3578, 221, 1760, 1907, 1854, 446, 2972, 980,  1782,
		   263,  2363, 890,  2966, 440, 1889, 1481, 1785, 281, 3679, 891,  2111,
		   743,  1781, 894,  3866, 54,  1994, 1684, 1797, 446, 3122, 1448, 1806,
		   377,  1787, 894,  3689, 450, 2312, 1493, 1794, 120, 3530, 896,  1796,
		   1208, 1794, 900,  2993, 225, 1796, 1562, 2306, 530, 3395, 900,  1800,
		   44,   1799, 1200, 3002, 449, 1920, 1772, 2561, 224, 3863, 882,  1817,
		   752,  1803, 923,  3476, 152, 1805, 1784, 1851, 446, 3017, 905,  2319,
		   443,  1799, 1016, 3017, 464, 2150, 2108, 1812, 57,  3602, 905,  1815,
		   803,  2339, 938,  3023, 271, 1929, 1714, 1836, 582, 3347, 909,  1844,
		   188,  1812, 899,  5390, 453, 1997, 1517, 1823, 228, 3041, 1178, 1907,
		   910,  1821, 1073, 3038, 8,   2378, 1526, 1941, 455, 3448, 915,  1827,
		   488,  2171, 912,  3032, 495, 1827, 1741, 2348, 108, 3056, 914,  2024,
		   902,  1826, 1176, 3597, 237, 1832, 1547, 1889, 459, 3932, 918,  2165,
		   110,  1946, 1002, 3422, 606, 1827, 1778, 1839, 228, 3469, 1097, 2364,
		   767,  1839, 923,  3068, 116, 1839, 2325, 1845, 459, 3632, 923,  1845,
		   380,  2621, 1022, 3503, 462, 1836, 1538, 1856, 44,  3278, 905,  1850,
		   875,  1848, 926,  4133, 230, 1850, 1547, 2189, 506, 3683, 1190, 1854,
		   197,  2108, 926,  3092, 462, 2460, 2072, 1857, 233, 3143, 927,  1860,
		   1031, 1857, 956,  3884, 60,  2231, 1556, 2391, 461, 3122, 939,  1863,
		   498,  1862, 1230, 3107, 551, 1863, 1553, 1881, 117, 4648, 1049, 1875,
		   797,  1862, 972,  3731, 299, 1863, 1765, 1871, 488, 3122, 938,  2784,
		   23,   1871, 1118, 3672, 467, 2087, 2072, 1875, 228};

void sol() {
	int n;
	cin >> n;
	int tot = 0;
	rep(i, n + 1) tot += ways[i];
	cout << tot << '\n';
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);
	sol();
#ifdef LOCF
	cout.flush();
	cerr << "- - - - - - - - -\n";
	(void)!system(
		"grep VmPeak /proc/$PPID/status | sed s/....kB/\' MB\'/1 >&2"); // 4x.kB
																		// ....kB
#endif
}