#include <bits/stdc++.h>
using namespace std;

const int N = 3e6+7; const int K = 21;
int anc[N][K];


const int MAXN = 3e6+7; ///max length of string+3
namespace PalTree {
  struct node {
    int len; ///length of the pal of this node
    int sufflink; ///largest suff pal of this node
    int chain;///#of nodes on chain of suff links
    int next[10];///next[c] is the pal by adding c
  } tr[MAXN];
  int occ[MAXN];



  int size;///# of nodes currently in Pal tr
  int suff;///max suff pal of curr prcessed prefix
  string s;///string we will built our Paltr on
  bool addLetter(int pos) {
    int cur = suff, curlen = 0, let = s[pos]-'0';
    while (true) {
      curlen = tr[cur].len;
      if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])
        break; cur = tr[cur].sufflink;
    }
    if (tr[cur].next[let]) {
      suff = tr[cur].next[let];

//        cout<<"child exists from "<<cur<<endl;
      occ[suff]++;
      return tr[ suff ].len;
    }
//    cout<<"child created from "<<cur<<endl;

    suff = ++size; tr[cur].next[let] = size;
    tr[size].len = tr[cur].len+2;
    if (tr[size].len == 1) {
      tr[size].sufflink=2; tr[size].chain=1;
      occ[size]++;
      anc[size][0] = 2;
      anc[size][1] = 1;

      return tr[size].len;
    }
    while (true) {
      cur=tr[cur].sufflink;curlen=tr[cur].len;
     if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos]){
        tr[size].sufflink = tr[cur].next[let];

        int par = tr[cur].next[let]; int u = size;
        anc[u][0] = par;
        for (int k=1; k<K; k++)
            anc[u][k] = anc[anc[u][k-1]][k-1];

        break;
      }
    }
    tr[size].chain=1+tr[tr[size].sufflink].chain;
    occ[size]++;
    return tr[size].len;;
  }

  void initTree() {
    memset(tr,0,sizeof tr);///CAREFUL:TESTCASES
    memset(occ,0,sizeof occ);
    anc[2][0] = 1;

    size = 2; suff = 2;
    tr[1].len = -1; tr[1].sufflink = 1;
    tr[2].len = 0; tr[2].sufflink = 1;
  }

//  int getanc(int u, int d) {
//      for (int k=0; k<K; k++)
//        if (d & (1<<k))
//          u = anc[u][k];
//      return u;
//  }

    void updatePath(int limit){
        int u = suff;

        for(int k=K-1; k>=0; k--){
            int v = anc[u][k];
            if(v==0 or tr[v].len<=limit){}
            else{
                u = v;
            }
        }
        u = anc[u][0];
        if(u) occ[u]--;
//        cout<<"found u = "<<u<<endl;
    }

}

typedef long long ll;

int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    s += s;

    PalTree::initTree();

    for(int i=0; i<2*n-1; i++){
        char c = s[i];

        PalTree::s += c;
        int curLen = PalTree::addLetter(PalTree::s.size()-1);
//        cout<<"inserted "<< i <<"; lastnod = "<<PalTree::suff<<endl;

        if(i>=n){
//                cout<<"updating path with tek = "<<i-n+1<<endl;;
            PalTree::updatePath(i-n+1);
        }
    }

    ll ans = 0;

    for(int i=PalTree::suff; i>2; i--){
        PalTree::occ[ PalTree::tr[i].sufflink ] += PalTree::occ[i];
        if(PalTree::tr[i].len <= n){
            ll tmp = 1LL * PalTree::tr[i].len * PalTree::occ[i] * PalTree::occ[i];
//            cout<<"for node "<<i<< " added "<<tmp<<"; occ = "<<PalTree::occ[i]<<"; len = "<<PalTree::tr[i].len<<endl;
            ans += tmp;
        }
    }

    cout<<ans<<"\n";

//  int q; cin >> q;
//  string operations; cin >> operations;
//  PalTree::initTree();
//  vector< int >subs, suffs; subs.push_back(0);
//  suffs.push_back(PalTree::suff);
//  for (char c : operations) {
//    if (c == '-') {
//      subs.pop_back(); suffs.pop_back();
//      PalTree::s.pop_back();
//      PalTree::suff = suffs.back();
//    } else {
//      PalTree::s += c;
//      PalTree::addLetter(PalTree::s.size()-1);
//      suffs.push_back(PalTree::suff);
//      subs.push_back(subs.back()+
//                PalTree::tr[PalTree::suff].chain);
//    }
//    cout << subs.back() << " ";
//  }
    return 0;
}

/*
5
01010
8
66776677

*/