RT

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,d[4000005],g[4000005],f[4000005],p,maxr,M,mod=51123987,ans;
string s,a;
void maracher(){
	for(int i=1;i<s.length();i++)d[i]=1;
	p=maxr=0;
	for(int i=2;i<s.length();i++){
		if(i<=maxr)d[i]=min(d[maxr+p-i],maxr-i+1);
		while((i+d[i]<s.length())&&(i-d[i]>=1)&&(s[i+d[i]]==s[i-d[i]]))d[i]++;
		if(i+d[i]-1>maxr){
			maxr=i+d[i]-1;
			p=i-d[i]+1;
		} 
	}
}
int main(){
	cin>>n>>a;
	s=' ';
	for(int i=0;i<n;i++){
		s+='#',s+=a[i];
	}
	s+='#';
	maracher();
	//cout<<s<<endl;
//	for(int i=1;i<s.length();i++){
//		cout<<d[i]<<' ';
//	}
	for(int i=1;i<s.length();i++){
		if(d[i]>=2){
			M+=d[i]/2;
			M=M%mod;
		}
	}
	M=(M*(M-1)/2)%mod;
//	cout<<endl<<M<<endl;
	for(int i=1;i<s.length();i++){
		f[i-d[i]+1]++,f[i+1]--;
		g[i]++,g[i+d[i]]--;
	} 
//	for(int i=1;i<s.length();i++)cout<<f[i]<<' ';
//	cout<<endl;
//	for(int i=1;i<s.length();i++)cout<<g[i]<<' ';
//	cout<<endl;
	for(int i=1;i<s.length();i++){
		f[i]=(f[i-1]+f[i])%mod;
		g[i]=(g[i-1]+g[i])%mod;
		//cout<<f[i]<<' '<<g[i]<<endl;
	}
//	for(int i=1;i<s.length();i++)cout<<f[i]<<' ';
//	cout<<endl;
//	for(int i=1;i<s.length();i++)cout<<g[i]<<' ';
//	cout<<endl;
	for(int i=2;i<s.length();i+=2){
		g[i]=(g[i]+g[i-2])%mod;
	}
//	for(int i=2;i<s.length();i+=2)cout<<g[i]<<' ';
	for(int i=2;i<s.length();i+=2){
		ans=(ans+f[i]*g[i-2])%mod;
	}
	cout<<(M-ans+mod+mod)%mod;
	return 0;
}