键盘上有左括号(，右括号)，和退格键-，共三个键。
牛牛希望按键n次，使得输入的字符串恰好一个合法的括号序列。
每按一次左括号(，字符串末尾追加一个左括号(
每按一次右括号)，字符串末尾追加一个右括号)
每按一次退格键-，会删掉字符串的最后一个字符，
特别的，如果字符串为空，牛牛也可以按退格，但是什么都不会发生。
输出方案数对p取模，注意p可能不是质数。
注：只要按键方法不同，就是不同的方案，即使得到的序列一样。
Solution
这题和其他关于括号序列的题不太一样，因为有了删除操作。
由于我太ZZ，然后搞了个*b方程。
设dp[i][j]表示按了i次，造出了一个长度为j的序列的方案数。
转移是dp[i][j]=dp[i-1][max(0,j-1)]+dp[i-1][j+1]
这里取max是指当序列为空时我也可以退格。
然后我们就有了一个长度为j的序列，我们要把左括号和右括号往里放，使得它是一个合法的括号序列。
其实这个方案数就是卡特兰数。
于是我们枚举长度，答案加上dp[n][i]*catalan(i/2)。
然后样例爆炸。
发现（+del和）+del最后制造出的序列是一样的，但是是两种不同的方案，但按照上面的方法dp只会计算一次。
所以删除时要考虑删什么字符。
正确转移方程：dp[i][j]=dp[i-1][max(0,j-1)]+dp[i-1][j+1]*2.
Code
#include<iostream>
#include<cstdio>
#define N 1002
using namespace std;
typedef long long ll;
int n;
ll f[N][N],dp[N][N],p,ans;
int main() {
scanf("%d%lld",&n,&p);
dp[][]=;
for(int i=;i<=n;++i)
for(int j=;j<=i;++j)
dp[i][j]=(dp[i-][max(j-,)]+*dp[i-][j+])%p;
f[][]=;
for(int i=;i<=n;++i) {
f[i][]=f[i-][];
for(int j=;j<=i;++j)
f[i][j]=(f[i-][j+]+f[i-][j-])%p;
}
for(int i=;i<=n;i+=)(ans+=(f[i][]*dp[n][i])%p)%=p;
printf("%lld\n",ans);
return ;
}