#include<bits/stdc++.h> #define int long long #define db long double using namespace std; #define y0 jp8akioi #define y1 jbhakioi #define yn baka24akioi #define fls fflush(stdout) template<typename T> inline void read(T &x){x=0;char c=getchar();bool neg=0;while(!isdigit(c)){if(c=='-')neg=1;c=getchar();}while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(neg)x=-x;} #define read2(a,b) read(a),read(b) #define read3(a,b,c) read2(a,b),read(c) #define read4(a,b,c,d) read3(a,b,c),read(d) #define read5(a,b,c,d,e) read4(a,b,c,d),read(e) #define read6(a,b,c,d,e,f) read5(a,b,c,d,e),read(f) int n,m,ans; string s[5000005]; struct solution{ int n; vector<string>s; vector<vector<int>>vis,nxt; vector<array<int,26>>ch; vector<int>lcp; solution(vector<string>ss):n(ss.size()),s(ss),lcp(n+1),vis(1),ch(1),nxt(n+1,vector<int>(m)){} int new_node(){ ch.push_back(array<int,26>()); vis.push_back(vector<int>()); return ch.size()-1; } void insert(int id){ int p=0; vis[p].push_back(id); for(auto it=s[id].rbegin();it!=s[id].rend();it++){ int c=*it-'a'; if(!ch[p][c])ch[p][c]=new_node(); p=ch[p][c]; vis[p].push_back(id); } } void sort(int p){ ::sort(vis[p].begin(),vis[p].end()); for(int i=0;i<26;i++)if(ch[p][i])sort(ch[p][i]); } int qu(int l,int r,int len,int id){ int p=0; for(int i=1;i<=len;i++){ int c=s[id][m-i]-'a'; if(!ch[p][c])return 0; p=ch[p][c]; } return upper_bound(vis[p].begin(),vis[p].end(),r)-lower_bound(vis[p].begin(),vis[p].end(),l); } void slv(){ ::sort(s.begin(),s.end()); s.insert(s.begin(),string()); for(int i=2;i<=n;i++){ while(lcp[i]<m&&s[i][lcp[i]]==s[i-1][lcp[i]])lcp[i]++; } for(int i=1;i<=n;i++)nxt[i][m-1]=m-1; for(int i=1;i<=n;i++){ for(int j=m-2;j>=0;j--){ if(s[i][j]<=s[i][j+1])nxt[i][j]=nxt[i][j+1]; else nxt[i][j]=j; } } for(int i=1;i<=n;i++)insert(i); sort(0); vector<int>st={n+1}; for(int i=n-1;i>=1;i--){ while(st.size()>1&&lcp[i+1]<=lcp[st.back()])st.pop_back(); st.push_back(i+1); for(int j=st.size()-1;j>=1;j--){ int L=st[j],R=st[j-1]-1; int res=qu(L,R,m-nxt[i][lcp[st[j]]]-1,i); ans+=2*(R-L+1)-res; } } } }; map<array<int,26>,vector<string>>buc; void slv(){ cin>>n; for(int i=1;i<=n;i++){ cin>>s[i]; array<int,26>bu={}; for(char c:s[i])bu[c-'a']++; buc[bu].push_back(s[i]); } m=s[1].size(); for(auto x:buc){ int m=x.second.size(); ans+=1337*m*(n-m); } ans/=2; // ans=0; for(auto x:buc){ int m=x.second.size(); solution(x.second).slv(); } cout<<ans<<endl; } signed main(){ // int T;read(T);while(T--) slv(); return 0; }