#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int N=1e7+20,M=1e6+20,mod=998244353;
int n;
namespace pam {
    int sz, tot, last;
    int cnt[N], ch[N][11], len[N], fail[N];
    char s[N];
    int node(int l) {  // 建立一个新节点，长度为 l
        sz++;
        memset(ch[sz], 0, sizeof(ch[sz]));
        len[sz] = l;
        fail[sz] = cnt[sz] = 0;
        return sz;
    }
    void clear() {  // 初始化
        sz = -1;
        last = 0;
        s[tot = 0] = '$';
        node(0);
        node(-1);
        fail[0] = 1;
    }
    int getfail(int x) {  // 找后缀回文
        while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
        return x;
    }
    void insert(char c) {  // 建树
        s[++tot] = c;
        int now = getfail(last);
        if (!ch[now][c - '0']) {
            int x = node(len[now] + 2);
            fail[x] = ch[getfail(fail[now])][c - '0'];
            ch[now][c - '0'] = x;
        }
        last = ch[now][c - '0'];
        cnt[last]++;
    }
    int c[N]; 
    void get() {
        for(int i=0;i<=sz;i++) c[i]=cnt[i];
        for (int i = sz; i >= 0; i--) {
            c[fail[i]] += c[i];
        }
    }
    long long solve() {
        long long ans = 0;
        for (int i = sz; i >= 0; i--) {
            cnt[fail[i]] += cnt[i];
        }
        for (int i = 1; i <= sz; i++) {  // 更新答案
//      	  cout<<cnt[i]<<' '<<len[i]<<'\n';
      	  cnt[i]-=c[i];
            if(len[i] <= n&&len[i]>=0) ans = ans  + 1ll * len[i] * cnt[i] * cnt[i];
        }
        return ans;
    }
}  // namespace pam
char s[N];
signed main(){
	// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    pam::clear();
    cin>>n;
    scanf("%s", s + 1);
    for(int i=n+1;i<=2*n;i++){
        s[i]=s[i-n];
    }
    pam::clear();
    for (int i = 1; i<=n; i++) {
        pam::insert(s[i]);
    }
    pam::get(); 
    for (int i = 1; i<=n; i++) {
        pam::insert(s[i]);
    }
    int ans=pam::solve();
    cout<<ans<<'\n'; 
	return 0;
}