#include<bits/stdc++.h> using namespace std; #define int long long #define ull unsigned long long #define pb push_back #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v const int MAXN=500010,N=30,base1=131,base2=171,Mod1=1011451423,Mod2=998244853; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} bool AAA; int n,m,ans,a[MAXN]; char s[MAXN],c[MAXN]; struct hs{int x,y;hs operator*(const int&G)const{return {x*G%Mod1,y*G%Mod2};}hs operator+(const int&G)const{return {x+G>=Mod1?x+G-Mod1:x+G,y+G>=Mod2?y+G-Mod2:y+G};}hs operator*(const hs &G)const{return {x*G.x%Mod1,y*G.y%Mod2};}hs operator+(const hs &G)const{return {x+G.x>=Mod1?x+G.x-Mod1:x+G.x,y+G.y>=Mod2?y+G.y-Mod2:y+G.y};}hs operator-(const hs &G)const{return {x-G.x<0?x-G.x+Mod1:x-G.x,y-G.y<0?y-G.y+Mod2:y-G.y};}bool operator<(const hs&G)const{return x==G.x?y<G.y:x<G.x;}bool operator==(const hs&G)const{return x==G.x&&y==G.y;}}jc[MAXN],h[MAXN]; hs qry(int l,int r){return h[r]-h[l-1]*jc[r-l+1];} int p[N]; map<hs,int>mp,ty; int cnt; vector<int>G[MAXN]; vector<pair<pii,hs>>Q[MAXN]; vector<pair<hs,int>>q[MAXN]; int id[MAXN],k,lp[MAXN],sp[MAXN]; bool cmp(int x,int y){ for(int i=1;i<=m;i++)if(c[a[x-1]+i]!=c[a[y-1]+i])return c[a[x-1]+i]<c[a[y-1]+i]; return 0; } void slv(){ n=read(); for(int i=1;i<=n;i++){ scanf("%s",s+1); a[i]=strlen(s+1)+a[i-1]; for(int j=a[i-1]+1;j<=a[i];j++)c[j]=s[j-a[i-1]],h[j]=h[j-1]*jc[1]+((hs){c[j],c[j]}),p[c[j]-'a']++; hs tp={0,0}; for(int j=0;j<N;j++){ for(int o=1;o<=p[j];o++)tp=tp*jc[1]+(hs){j+'a',j+'a'}; p[j]=0; } if(!ty.count(tp))ty[tp]=++cnt; G[ty[tp]].pb(i); id[i]=i; } m=a[1]; for(int i=1;i<=cnt;i++)ans+=6666*G[i].size()*(n-G[i].size()); ans/=2; for(int i=1;i<=cnt;i++)ans+=G[i].size()*(G[i].size()-1); for(int e=1;e<=cnt;e++){k=0; for(auto o:G[e])id[++k]=o; sort(id+1,id+k+1,cmp); // for(int i=1;i<=k;i++)cout<<id[i]<<" ";cout<<endl; for(int i=1;i<=k;i++){ int it=k; lp[0]=k; for(int j=1;j<=m;j++){ while(c[a[id[it]-1]+j]!=c[a[id[i]-1]+j])it--; lp[j]=it; } for(int j=m;j>=1;j--)sp[j]=j==m||c[a[id[i]-1]+j]>c[a[id[i]-1]+j+1]?j:sp[j+1]; sp[0]=sp[1]; // cout<<i<<":"<<endl; // for(int j=1;j<=m;j++)cout<<sp[j]<<" ";cout<<endl; for(int j=0;j<m;j++)if(lp[j+1]<lp[j]){ if(sp[j+1]!=m) Q[sp[j+1]+1].pb(mk(mk(lp[j+1]+1,1),qry(a[id[i]-1]+sp[j+1]+1,a[id[i]]))), Q[sp[j+1]+1].pb(mk(mk(lp[j]+1,-1),qry(a[id[i]-1]+sp[j+1]+1,a[id[i]]))); else ans-=(lp[j]-lp[j+1]); // cout<<j<<" "<<lp[j+1]+1<<" "<<lp[j]<<" "<<sp[j+1]<<" "<<qry(a[id[i]-1]+sp[j+1]+1,a[id[i]]).x<<endl; } if(lp[m]!=i)ans-=2*(lp[m]-i); } for(int i=1;i<=m;i++){ for(auto o:Q[i])q[o.fr.fr].pb(mk(o.sc,o.fr.sc));Q[i].clear(); mp.clear(); for(int j=k;j>=1;j--){ mp[qry(a[id[j]-1]+i,a[id[j]])]++; for(auto o:q[j])ans-=mp[o.fr]*o.sc; q[j].clear(); } } } printf("%lld",ans); } bool BBB; signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); jc[0]={1,1};for(int i=1;i<=MAXN-5;i++)jc[i]=jc[i-1]*((hs){base1,base2}); slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"<<((&AAA)-(&BBB))/1024.0/1024<<"MB\n"; return 0; }