rt，代码如下：

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
const int N=1e4;
int n,f[N][N],ans;
char s[N];
il int read() {
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
signed main(){
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	n=read();
	if(n<=8000) {
		scanf("%s",s+1);
	//	memset(f,0x3f,sizeof(f));
		for(int i=1;i<=n;++i) f[i][i]=0;
		for(int i=1;i+1<=n;++i) {
			int j=i+1;
			if(s[i]==s[j]) f[i][j]=1,ans++;
		}
		for(int len=4;len<=n;len+=2) {
			for(int i=1;i+len-1<=n;++i) {
				int j=i+len-1;
				if(s[i]==s[j]) {if(f[i+1][j-1]==1) {f[i][j]=1;ans++;}}
				for(int k=i;k<=j;++k) {
					if(f[i][k]&&f[k+1][j]) {
						if(!f[i][j]) {
							f[i][j]=1;
							ans++;
							break;
						}
					}
				}
			}
		}
		printf("%lld",ans);	
	}
	else {
		string s1;
		cin>>s1;
		puts("0");
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}