# 11075: 【原1075】括号匹配 11.07

### 题目描述

author: lsz 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1075

## Description

1 空串是合法的

2 如果P是合法的，那么aP也是合法的

3 如果P是合法的，那么(P)也是合法的

4 如果P和Q都是合法的，那么PQ也是合法的

## Input Format

$$N. (0 < N \leq 3333)$$

## Sample Input 1

1


## Sample Output 1

1


## Sample Input 2

3


## Sample Output 2

4


## Sample Input 3

4


## Sample Output 3

9


## FineArtz's solution

/* 括号匹配 11.07 */
#include <iostream>
using namespace std;

const int MOD = 19301;

int main(){
long long f[3335] = {0};
int n;
cin >> n;
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; ++i){
f[i] += f[i - 1];
for (int j = 1; j <= i - 1; ++j){
f[i] += f[j - 1] *  f[i - j - 1];
f[i] %= MOD;
}
f[i] %= MOD;
}
cout << f[n] << endl;
return 0;
}


## ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cmath"
#include "cstring"
using namespace std;

constexpr long long mod = 19301;
long long tree_num[3350] = { 0 };

long long jc[3350] = { 0 };

long long fast_pow(long long a, long long b) {
long long ans = 1, base = a;
while (b) {
if (b & 1)
ans = (ans * base) % mod;
base = (base * base) % mod;
b >>= 1;
}
return ans;
}

long long get_zhs(int n, int m) {
long long temp = (jc[m] * jc[n - m]) % mod;
temp = fast_pow(temp, mod - 2);
temp = (jc[n] * temp) % mod;
return temp;
}

long long cal_tree(int n) {
if (n == 0)
return 1LL;
if (tree_num[n] > 0)
return tree_num[n];
long long ans = 0;
for (int i = 0; i < n; ++i) {
ans = (ans + cal_tree(n - i - 1) * cal_tree(i)) % mod;
}
tree_num[n] = ans;
return ans;
}

int main() {
jc[0] = 1;
for (long long i = 1LL; i <= 3350LL; ++i) {
jc[i] = (jc[i - 1] * i) % mod;
}
long long n;
cin >> n;

long long ans = 0;
for (int i = 0; i <= n; i += 2) {
ans = (ans + get_zhs(n, i) * cal_tree(i / 2)) % mod;
}

cout << ans;

return 0;
}


## q4x3's solution

/**
* 括号匹配
* dp
* 按第一个字符分类:
* ‘a’: f[n - 1]
* '(': 按对应')'位置，若为j，则f[j - 1] * f[n - j - 1]
**/
#include <iostream>

using namespace std;

int f[3340];
int main() {
int N;
cin >> N;
f[0] = 1;
f[1] = 1;
for(int i = 2;i <= N;++ i) {
f[i] += f[i - 1];
for(int j = 1;j < i;++ j) {
f[i] += (f[j - 1] * f[i - j - 1] % 19301);
f[i] %= 19301;
}
}
cout << f[N] << endl;
}


## victrid's solution

#include <iostream>
using namespace std;
int main() {
unsigned short ans[3335] = {1,1,2,4,9,21,51,127,323,835,2188,5798,15511,3233,17129,1756,4223,2057,12644,17742,13185,9674,16560,14982,14280,15456,9603,3212,14660,18549,2234,2214,12614,4301,15589,17775,10176,12374,6701,13423,3195,16695,13109,33,12490,11545,12863,10973,13555,5069,19213,9441,2024,10011,10412,12158,2060,3304,16174,6172,14014,16503,2036,12600,9402,17905,12310,15883,19283,16513,12181,9760,6455,9879,3430,16409,16099,763,4556,18296,3898,4284,1769,6337,4109,3803,6662,4606,10364,12751,1667,8546,1333,13840,13630,12355,6264,9678,622,15638,3108,10635,510,4426,17861,2490,16795,13477,4710,18897,13299,2348,308,2601,6534,17534,15451,18533,7488,6482,2126,15169,9578,6210,1720,17030,10050,12314,15493,16633,18653,11212,6733,7174,18474,9553,5562,18216,11838,3812,7511,14048,11667,6861,11376,18655,7379,18151,14399,9025,10694,16311,2725,2827,8421,15411,7671,9210,12963,1610,5259,18241,5738,5793,17571,17683,5482,11695,1078,3761,1769,13479,11309,8456,5483,1789,3021,7171,8337,15832,750,13400,4249,15322,15232,17442,10787,9787,12058,1795,18965,13935,3481,15704,15552,6720,17176,7103,6276,1473,11822,16984,10192,11785,18019,4045,8788,6231,1137,19130,4844,9114,10061,2864,8377,29,1292,13228,4832,7609,13505,3649,3,10807,7815,1690,8971,18951,13195,2372,11424,19205,3948,4276,17574,6546,514,6119,4275,1558,3560,493,1008,8664,3733,11608,18029,8389,14374,6228,6738,16906,12250,12714,13949,5351,7563,8251,232,18718,16546,3507,2751,6113,11900,8402,589,1127,17714,12366,799,9222,12613,4165,14663,15258,6451,14324,15311,3392,9689,9224,12926,16120,18073,555,2887,16341,6875,1707,807,9441,13304,1250,5349,319,17427,704,11662,16578,3847,17340,16921,3740,6807,18308,4710,15981,8008,12343,5861,16891,140,17014,9973,10133,13026,3101,3689,12050,8158,5505,14297,15784,9089,9057,14685,17616,10471,14730,15401,7858,10985,3867,15200,11465,16459,3665,3218,19287,3785,16780,2084,18639,3987,13146,9917,9185,15141,14416,6685,7203,14929,15764,11450,1415,12781,2353,13115,8955,8229,11290,892,12683,11621,12501,10597,17664,4381,1098,5418,2262,14127,17579,15051,18509,479,13773,9054,16325,3538,1869,15310,5784,16994,951,11045,13672,9194,4275,8660,11122,15120,15254,18968,3574,16653,18281,4945,10859,640,5209,9753,15644,7494,16989,6640,10263,15228,13995,767,6616,12811,1609,6008,4268,14764,5237,17051,17671,11363,16695,7760,17966,203,5694,11096,5064,776,7363,10419,6908,8920,290,9358,5824,3003,17007,16877,8816,18821,8451,2243,12217,16668,18203,9137,14812,1810,4610,15779,17966,8907,13607,13036,5849,9676,8968,4254,14401,19204,12340,14619,11633,2650,18177,4421,3241,7402,16550,1573,18929,18240,2627,14239,17890,953,5148,16362,14865,16871,16216,13203,5347,939,16348,8619,18327,17021,13148,16593,12820,1781,8557,13812,6610,4370,15699,18356,18464,2895,10222,4086,14018,18930,16054,3665,14954,12253,11243,11239,18245,10724,8979,16114,11876,18239,11995,1712,18335,9170,17731,15234,772,8012,3192,8771,14025,14950,16585,18791,11594,1433,8764,18333,10844,1376,12285,19278,3711,3202,15645,13118,382,14872,2327,10728,8090,12069,17875,9774,11017,10271,9749,11143,14550,16509,2076,635,11177,15672,16686,12085,7079,6057,5021,906,7700,17860,7158,19055,7633,7666,15246,3832,10662,11534,6426,10104,17276,13481,17770,9155,6963,2481,1071,11708,7678,15128,4011,15760,5559,8124,783,12631,15218,7287,15142,3997,13929,7466,6445,5650,3394,1852,15321,5461,14797,18296,14022,12770,15417,5666,15150,14430,18462,6458,402,12860,19119,1663,8599,12100,7847,11238,19254,4354,9805,9310,3376,14927,3914,11676,2582,138,2137,14266,15998,6603,15417,3218,15265,3414,5174,4982,13160,5572,16810,10926,3245,14976,2272,11893,16431,7634,5693,12598,14316,16182,1110,16254,13479,10763,12246,5198,12655,13357,3430,1883,11873,16392,16090,13827,11054,8565,8255,4136,4171,18321,3445,9806,14316,7574,14370,5270,9274,17753,19037,13479,5134,9702,14895,14180,2252,15570,17862,15792,9822,14221,13750,18865,8850,17950,2715,17075,583,2774,3630,13248,881,10296,2120,8714,17705,12981,18717,16889,4018,15450,10930,1568,16082,18174,15368,5213,1548,6495,670,17966,8024,4670,19286,13318,382,1532,12239,7900,15980,11159,13366,15825,1358,10536,6952,8773,2394,2479,11689,17305,18581,17341,13545,6051,17733,4305,8395,12153,14861,17218,4133,4153,9459,7291,5958,2108,4573,10376,92,13644,18723,16768,8947,14928,6278,12223,11265,15252,13541,1122,12260,4576,7985,19152,7781,14645,10232,18953,14253,1441,14460,5317,17540,1631,4038,8983,12419,13037,12317,12501,1913,6382,3339,2190,18931,10261,1512,10588,9194,17689,13005,18648,18124,9214,12721,15398,5473,15871,13612,11414,14386,15218,16557,5015,12899,5738,6322,10192,3902,8583,7059,13581,4607,12997,7219,14615,16790,15781,11899,10407,2827,4295,14072,3406,5947,16237,9587,11369,3207,2741,13812,13682,6585,12938,5763,1097,10928,19226,12320,2042,13537,16719,8857,17135,17357,12956,17985,1062,11690,13603,16792,4937,4611,4577,5939,9810,16677,10461,2172,12912,5787,13723,4307,10852,1700,7041,15420,18128,10631,10042,2641,8575,18728,10116,14409,7037,1231,5358,13885,8938,924,4390,14029,6144,6933,8631,10406,522,2728,51,3958,14341,18928,8223,7963,14023,14977,4220,9295,15339,5926,5805,12917,15327,13601,5499,9114,1635,1328,3992,16752,17720,7839,15430,6175,11271,12051,10236,2212,12030,10433,11137,2494,7023,12291,15798,10338,14382,10721,1456,3308,13636,6702,2086,13618,1694,16821,14781,10768,3642,1878,4811,2296,17191,19134,12837,13618,14043,18695,8733,8431,897,88,12826,14889,5779,16184,15559,6942,17009,12998,9667,7561,7881,181,18843,3968,420,3222,4883,18531,18690,13562,13275,4379,18917,10356,15471,1359,1044,12744,3146,10051,4625,4615,6550,18355,4835,3402,5987,13541,16761,18911,6128,2210,17538,12427,14349,7280,18119,13763,16528,4273,18899,12939,5506,7959,578,14439,7310,16754,789,3187,2117,2740,5489,16534,13571,15965,5557,62,1206,9626,6415,17208,9917,18356,6157,12671,15710,13158,1354,1924,18807,177,10884,2783,1504,339,7598,11659,14228,1215,4157,9871,13682,9462,10166,14323,18847,7611,285,1609,6007,2932,12759,6996,238,15341,18216,8358,4938,9952,11823,13753,17519,14574,3695,5414,18273,18850,3076,2428,16522,7266,11393,14706,4447,13452,8220,11067,12631,17724,12612,961,18659,7242,12892,16037,1901,18353,17350,2007,2087,17080,17581,961,18543,18489,19237,14316,14778,11525,11341,5202,6389,16303,12974,1677,4369,11901,11540,16240,3650,18640,7545,15384,14175,11492,10359,6646,2406,7670,12666,7590,5463,18528,7,1531,4858,9522,9429,5258,4546,18296,16721,3667,8255,5479,17209,6281,10887,16858,4715,19139,15490,14578,17434,6607,19290,3035,6194,7879,1704,14217,10109,16868,16018,3302,3298,3198,15375,6818,8652,11347,14429,8028,19003,1968,15885,4365,11240,7622,1820,15671,487,75,8986,16532,6353,1479,1059,10440,2077,15305,394,790,9979,18418,16965,7450,18688,18047,14278,2417,7256,1776,13187,702,16012,1601,8834,1369,6985,16490,8708,488,13518,1954,11782,2948,7466,16880,15740,17023,4234,14310,2561,1769,17362,2494,3608,3631,131,5966,19048,1593,5116,15559,6570,4980,10464,517,17897,14368,7596,18145,14226,5826,2929,5364,7445,72,9248,5217,1,18815,8089,3434,19261,6781,16021,15168,11545,9376,19174,2265,13931,10418,13847,14545,10489,1950,18378,2881,13979,4065,11208,16693,3469,3684,7061,9727,15835,8403,7887,17275,17046,12744,7381,12106,7007,15526,1383,4908,333,4590,1888,7115,8181,6590,8156,15453,2800,12100,9439,18802,1892,16407,4356,10998,14482,19003,14413,5789,11650,11439,11956,4622,11643,4873,5027,1317,2110,11020,16109,11480,17188,4700,7429,239,12532,9181,17467,15595,2880,15079,3193,10481,18058,13532,429,5286,9806,6597,9695,17852,15978,9944,18789,5897,938,12035,7989,7615,3182,15075,7516,10613,4719,610,13952,15403,13749,16361,9993,13308,7688,18218,752,1433,8396,12983,5845,18657,15918,2613,9722,8486,14342,9113,9185,14455,14145,17364,1061,5799,9543,6101,4774,7550,10322,13536,11670,7156,17082,11639,5123,11914,9284,17541,7272,4957,2203,5696,10001,15239,14297,3509,4141,7192,5958,10091,6267,14896,6983,17103,13067,17676,2912,17624,12659,3152,15728,2217,4351,542,16028,6377,7687,5424,16088,15878,5757,4046,9902,15183,5475,888,14691,5433,10253,10648,7487,13050,7566,3370,1108,3003,11181,6480,14697,19265,19051,13964,16908,16027,17126,5390,17059,1292,2294,4206,2020,3726,14669,5625,8954,12141,7103,1552,807,1040,13065,1728,16890,14128,19258,4194,18549,2627,18896,10805,10764,14441,326,5711,15801,8831,8362,13225,4492,4036,6216,5164,17471,15186,4333,4395,6058,5668,7481,18829,19250,11021,18761,17796,2204,7928,11519,14013,4356,3516,3046,2147,8515,2548,11828,12289,16560,7693,18024,8660,910,3354,13799,10150,12340,7603,6130,5604,2590,827,13345,18684,18225,17512,14562,14855,1346,689,17955,15058,11227,17349,6830,14868,16982,5591,8459,17445,12859,3243,12255,10789,201,14662,2805,2232,1192,17579,11989,16983,12346,1809,14729,16280,15977,15996,5053,18256,5478,17400,7962,1169,3675,2926,11758,13598,9646,1821,14785,4753,9524,18245,7978,4331,15259,12714,10454,2804,17099,4478,12558,3940,16681,5626,2748,15188,10476,16380,7106,9341,9987,16017,5416,3280,10485,15930,499,16824,11324,8681,8030,17026,12342,7967,18389,15210,11344,17162,18945,4951,2909,5658,17079,19141,12681,18689,6069,18304,595,15801,14547,412,10649,19067,3395,11596,11615,6893,4462,3776,15539,18578,8374,7707,6403,7498,1845,11092,5566,16843,2477,5344,15582,7634,10956,5677,1679,12039,14447,2991,2544,10595,1715,7671,15219,16551,341,12769,6960,849,8224,17922,17717,1080,16807,2296,9248,1660,10342,14795,16931,19074,8848,3284,8916,9395,18555,9352,7971,12960,7802,7038,1768,4359,9903,5173,17713,1117,7296,18668,16362,17621,5219,9748,3708,4771,7453,1009,2009,6857,1358,8278,17880,18375,3511,10695,2031,7220,3694,5315,8961,10329,9186,18088,6152,18461,9957,16328,10871,8501,14196,3799,3114,8850,14114,11670,7532,5072,15639,16207,4682,18731,6420,9606,12205,6930,8454,5162,5379,6382,5196,7254,2603,12115,1569,15928,18372,6776,14320,1457,8274,16385,10411,8791,3046,3708,6318,2208,10662,16098,8059,1808,8524,11637,19152,3699,2805,4269,8186,8648,9458,1801,7305,1883,19179,8314,14576,219,39,6932,863,19246,11452,14955,10989,7407,13932,4858,7656,13050,13641,179,11135,14874,1635,1818,1414,16538,17326,12235,12884,11807,11880,11659,11462,18157,6794,17055,10129,8397,6516,6101,1842,7129,1964,88,1233,4730,8210,1732,6887,12297,18707,15622,2368,5968,11361,5574,12057,9437,2440,2114,8101,4311,4187,11198,18077,10932,12645,949,1127,16758,7789,10006,17112,10043,12151,3279,14367,6649,950,3964,9265,9154,1923,5838,2653,16662,18261,7750,2968,15823,5337,8349,16886,7358,6950,18505,14758,18972,11660,14667,2515,18027,14963,8188,10704,9812,4422,13682,16218,18194,5748,469,12115,15485,13979,2356,7604,14353,12888,9393,3612,1282,16883,17132,2808,7434,16298,16567,6959,15203,479,9606,580,15404,6440,5825,6505,4347,12823,3157,8569,16248,9288,6988,6129,13193,4373,14314,6111,8240,3579,12236,89,6536,16387,9075,7776,18975,17366,12246,2366,1664,10314,4463,14949,7368,9657,11125,18,9138,19121,16837,12543,3404,16246,5795,1745,11034,4604,3338,5869,5180,4660,9293,8346,18395,14133,18844,16770,1585,7190,12162,1144,11789,9170,17665,4026,10796,609,527,12644,9267,13533,13905,9575,1554,2759,14958,17557,5463,1489,6848,8659,10332,7956,2758,6916,13943,1269,8948,6720,10407,1724,16753,12226,12580,2201,1897,3404,10198,14573,18186,16072,6692,17060,258,6958,15590,17099,15829,17464,4291,13301,17911,16999,2470,11141,13283,9515,4273,13893,13684,404,14614,14204,11853,15023,15309,7209,9155,10321,13494,8452,1249,15026,16943,7183,9163,10430,18590,11298,16808,16160,5686,8472,7637,8775,15835,12371,12425,2036,17157,3932,2299,17348,9838,1769,16495,18872,15953,6356,6798,13825,10788,4602,18171,7985,4320,6700,12144,4819,14174,18946,11683,11753,429,2349,4080,13439,4578,3796,14275,8194,2418,17488,4434,4061,17298,6720,3077,367,6496,4049,16167,18421,16480,11909,2304,11248,7629,15471,282,8028,7860,14858,4849,13473,4969,15309,17756,11275,12604,17143,11059,7836,18916,4567,11802,16753,11179,2918,774,10720,2413,12421,10949,7756,9808,14666,18167,1636,4087,12989,7755,16936,116,15974,6387,4671,15775,7294,14195,12359,6868,13351,1527,16604,11353,16759,8752,1450,1873,16515,13560,9246,2926,18705,18662,5872,1739,8309,11279,8851,18548,11263,13498,7757,11452,12883,8635,6389,18925,12866,14740,15489,17275,7092,16200,2973,18316,3211,11285,17017,15072,13150,18143,15303,18185,10428,9961,8951,15686,17973,3381,9482,255,18346,9743,8020,9410,175,5254,2267,17700,6102,11102,4774,6258,17756,19262,248,10698,18399,16447,17443,2722,14285,565,11621,2420,6869,18763,10532,2480,11445,17649,13512,2293,16182,11335,15415,4164,15810,5780,14937,6657,15871,2607,16375,10910,11506,13429,12575,1331,13365,359,1427,8080,8839,829,7532,19089,9230,6913,13611,4863,19120,13574,5132,7526,12738,8106,7395,8028,12065,15681,7464,18988,15267,6188,16506,11693,17466,18655,1158,7576,10093,10228,19293,6035,630,11560,11629,17487,6977,6848,10256,9799,15273,12779,11548,16827,10803,17900,12795,2183,10630,8760,11204,11507,7137,8215,14373,10736,8731,16356,7792,7346,270,223,2304,16497,12526,1996,1779,11185,11055,4674,13159,10864,16541,8473,6323,14459,4183,17727,1189,14837,6898,11747,14974,3922,15919,10465,6997,16916,10461,743,18279,13331,2006,17630,8645,7107,6929,6090,3892,13728,7750,5440,12502,11041,12232,430,8136,6250,15332,4735,18978,2665,9989,7388,14023,17735,7625,5826,13084,5659,5212,3253,15247,15099,11215,15007,11775,14118,5540,10459,14229,8801,7857,2486,2148,3065,9655,5402,140,1524,11509,8293,2328,1504,13334,10293,8724,15416,8182,9899,16807,5247,13254,12701,11147,7026,6625,3020,14276,18901,7291,15261,7995,2893,18987,5453,13700,14988,15001,5660,15645,14246,97,8663,4786,12329,15830,13845,4332,14523,3194,16243,9022,12523,3874,14647,17558,9111,18523,6044,18413,7307,10559,2645,15763,13635,1360,17399,13250,9390,505,11014,14727,8026,7758,16237,6148,11953,8276,10522,9232,11837,13815,6622,3035,14075,3741,13963,16890,8428,9490,18864,15244,8437,11136,15564,11330,3801,18566,6936,8000,13150,19186,4097,2950,218,3308,18357,18690,6096,16135,4655,7911,1166,6742,6419,17063,2756,12318,5087,5379,17739,6371,14340,1295,14946,14858,9839,14723,1160,6866,10827,14443,7783,13297,15912,10471,16312,11461,11751,10443,17923,2846,18428,6836,14410,12229,6595,4856,12299,1069,260,15299,1566,8402,12300,18986,11839,2018,18348,18949,9737,16219,3332,12532,8708,11940,1358,12813,395,18623,13103,4461,15802,12333,15499,562,6676,1543,1479,1694,5003,14830,15806,11596,2552,9146,13019,16726,637,9123,18560,8637,8875,71,4279,9330,13239,16627,9301,6198,15387,12260,19063,17331,14258,9241,17708,7142,9879,18074,15341,12202,8482,142,15199,14857,15704,4249,11975,15470,14859,9460,5378,187,4574,9960,537,11435,8024,4998,9753,534,10004,613,14462,15852,9373,15764,11509,10581,8126,5562,8715,14604,2322,9088,11742,6,1827,12375,9405,10871,13679,12298,7815,9859,215,18068,18865,1976,14079,7559,7581,3558,2176,19132,12195,15953,18739,15233,12285,9791,277,8618,9800,1065,7897,12802,17623,16801,11777,18284,15696,14562,7531,15791,14648,1597,12334,5088,8744,10847,9111,10455,13289,3293,11719,10849,18459,13347,9443,2467,11632,8998,14733,2079,3104,5453,15926,6878,15855,2836,14487,15024,9458,2264,3672,10806,16684,16119,16615,9820,17037,5969,1257,16667,13633,17754,431,8467,9148,17607,14000,11009,14661,759,1935,11844,8301,5374,13195,3885,6956,1589,9881,19207,1008,3711,5510,4621,16137,331,1135,5906,3748,10631,11126,3959,10596,15636,12449,18465,2544,4114,2966,14662,8942,484,19071,13640,7275,4280,16762,9731,4696,3883,1326,12726,4320,2721,17401,8894,5270,4207,12680,1863,10327,1754,7420,4421,8582,8721,14410,4452,11557,6382,1285,7704,6381,12377,6087,4136,17694,2357,3235,8090,13136,11804,4434,13002,1821,692,6861,1823,8396,17421,12714,16648,14810,1184,17658,5038,16098,6682,1609,6634,8988,5829,9755,13935,15730,17758,10114,11125,16618,11095,12385,15004,8689,6731,7161,3100,17610,11867,18078,12355,13172,16491,654,19234,4902,17728,12188,14753,3536,10823,14327,11385,16373,4632,12166,5983,14355,16745,10678,5682,3607,17807,6090,12854,18918,12583,14103,15603,8204,9137,8302,10258,1682,6692,15434,10379,300,17663,16565,12329,2686,4777,13976,17944,1390,7036,3200,5984,6918,1879,38,1537,713,15682,17592,18907,1102,15385,2574,1687,6697,7427,9235,8038,3083,13592,2115,6221,19270,973,13660,10703,12915,10340,4639,10835,8440,13213,12808,1508,14275,13971,14813,3592,11512,14634,11923,17310,15479,19185,2299,2024,14379,10401,2272,1376,9671,2564,17812,17852,17835,8713,12187,8383,2217,13088,7638,3519,14427,5948,17190,2522,17384,1089,7459,16287,16427,17295,8693,740,13597,12974,11859,3576,6741,14717,15422,5826,12791,18981,4130,3957,9178,6707,11836,7195,17256,1585,4543,8887,15777,8075,9856,4740,14164,8891,14047,3802,4584,1064,17010,5765,18271,13182,1914,2997,15065,957,18429,1747,2225,16412,11053,14410,13804,8309,2451,15374,16169,15721,15983,6282,5640,346,3226,15446,15142,11621,13697,8319,17155,11202,12754,12845,4097,19223,11659,9407,14364,13321,12080,14068,6601,17130,17098,9886,14471,17162,8880,5892,1555,4938,15031,917,730,5616,9020,13706,5211,574,18827,3042,7893,12933,6285,18313,14596,18768,1625,16790,6475,12769,5042,17501,5412,5173,1414,16280,117,5480,16342,2925,17751,15525,17912,16484,18060,352,6263,9621,1768,10278,13171,4826,8724,10246,17886,4610,3592,18295,13877,14963,19017,8530,11035,13242,3772,4192,8169,18747,7239,9232,2783,12723,12714,10111,3071,13143,14549,1998,4260,11141,14366,5831,17266,11667,13619,9744,691,15718,14530,12188,2044,12458,6650,16412,4256,126,5623,7211,15912,13609,14751,4601,8743,13942,5997,13143,4254,9900,16688,6476,4545,7597,1714,14472,7919,9327,6582,2443,17931,6323,5074,39,668,16687,15072,11877,14984,10114,4705,11029,14263,17165,8290,8262,13040,7151,8626,9889,15345,10394,16871,6121,1305,12558,14190,6407,9001,8130,14469,5819,4688,5088,13022,7088,13836,4652,1035,11627,10662,9031,18946,298,2055,18589,2479,4031,590,7543,2896,4331,14112,7472,3677,11759,10349,15855,11178,6143,6444,16252,1661,2695,9522,662,10191,13047,5723,8848,14823,12587,3938,6119,373,14493,14224,3414,6112,10906,10029,14319,1263,19049,1652,5544,13187,3598,7830,19144,13501,630,3040,4110,7366,12248,5667,18341,1581,2906,16372,16150,2549,19068,10526,17856,12266,4769,12065,18616,492,1638,15983,6860,8737,4816,1789,17440,4891,10343,4511,7168,2476,5605,10042,15782,11085,13444,17995,19193,14766,5051,4605,15591,8641,70,10444,15552,17894,4304,8550,9955,7697,5069,17640,3781,7471,8729,17532,9122,4446,10005,10810,16275,11487,13888,16888,12144,19109,15319,269,19146,15174,9750,3534,16175,5840,4915,3692,6063,5902,11070,1027,18381,70};
int n;
cin >> n;
if(ans[n]!=0){
cout << ans[n];
return 0;
}
long long tmp;
for (int i = 2; i <= n; i++) {
tmp = ans[i - 1]; /*add a at back*/
for (int j = 0; j < i; j++) {
/*add ) at back. the ) must not belong to any original pairs.*/
/*a ( should be inserted between legals*/
tmp += ans[j] * ans[i - j - 2];
tmp %= 19301;
}
ans[i] = tmp;
}
cout << ans[n];
return 0;
}


## yyong119's solution

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

int num[4000];

int main(){

int n;
cin >> n;
memset(num, 0, sizeof(num));
num[0] = 1;
num[1] = 1;
for (int i = 2; i <= n; ++i){
num[i] += num[i - 1];
for (int j = 1; j < i; ++j){
num[i] += num[j - 1] * num[i - j - 1];
num[i] %= 19301;
}

}
cout << num[n] << endl;

return 0;
}


## zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
#define M 19301
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, f[3335][2000] = {0};
void init(){
cin >> n;
}
void solve(){
f[0][0] = 1;
int hf = (n >> 1);
for (int i = 1; i <= n; ++i){
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % M;
for (int j = 1; j < hf; ++j)
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j] + f[i - 1][j + 1]) % M;
f[i][hf] = (f[i - 1][hf - 1] + f[i - 1][hf]) % M;
}
cout << f[n][0] << endl;
}
int main(){
init();
solve();
return 0;
}