Problem: You are given a string s. Each pair of numbers l and r that fulfill the condition 1 ≤ l ≤ r ≤ |s|, correspond to a substring of the string s, starting in the position l and ending in the position r (inclusive).

Let's define the function of two strings F(x, y) like this. We'll find a list of such pairs of numbers for which the corresponding substrings of string x are equal to string y. Let's sort this list of pairs according to the pair's first number's increasing. The value of function F(x, y) equals the number of non-empty continuous sequences in the list.

For example: F(babbabbababbab, babb) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are: 

  * (1, 4)
  * (4, 7)
  * (9, 12)
  * (1, 4), (4, 7)
  * (4, 7), (9, 12)
  * (1, 4), (4, 7), (9, 12)



Your task is to calculate for the given string s the sum F(s, x) for all x, that x belongs to the set of all substrings of a string s.

Input

The only line contains the given string s, consisting only of small Latin letters (1 ≤ |s| ≤ 105).

Output

Print the single number — the sought sum.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

aaaa


Output

20


Input

abcdef


Output

21


Input

abacabadabacaba


Output

188

Note

In the first sample the function values at x equal to "a", "aa", "aaa" and "aaaa" equal 10, 6, 3 and 1 correspondingly.

In the second sample for any satisfying x the function value is 1.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
public class CF123_D1_D{
	public static void main(String[] args)throws Throwable {
		MyScanner sc=new MyScanner();
		PrintWriter pw=new PrintWriter(System.out);
		
		char [] s=sc.next().toCharArray();
		SA=new SuffixAutomaton(s);
		int n=SA.idx+1;
		acceptState=new boolean [n];
		int cur=SA.lst;
		while(true){
			acceptState[cur]=true;
			if(cur==0)
				break;
			cur=SA.link[cur];
		}
		cnt=new long [n];
		Arrays.fill(cnt, -1);
		long ans=0;
		for(int i=0;i<=SA.idx;i++){
			long x=dfs(i);
			int cnt=SA.len[i]-SA.len[SA.link[i]];
			ans+=(x*(x+1)/2)*cnt;
		}
		pw.println(ans);
		pw.flush();
		pw.close();
	}
	static SuffixAutomaton SA;
	static boolean [] acceptState;
	static long [] cnt;
	
	static long dfs(int u){
		if(cnt[u]!=-1)
			return cnt[u];
		long ans=acceptState[u]? 1 : 0;
		for(Entry<Character, Integer> e : SA.nxt[u].entrySet()){
			int v=e.getValue();
			ans+=dfs(v);
		}
		return cnt[u]=ans;
	}
	
	static class SuffixAutomaton {
		int [] link,len;
		TreeMap<Character, Integer> [] nxt;
		int lst, idx;
		
		SuffixAutomaton(char [] s){
			int n=s.length;
			link=new int [n<<1];
			len=new int [n<<1];
			nxt=new TreeMap [n<<1];
			nxt[0]=new TreeMap<Character, Integer>();
			for(char c : s)
				addLeter(c);
		}
		
		void addLeter(char c){
			int cur = ++idx;
			int p=lst;
			while(!nxt[p].containsKey(c)){
				nxt[p].put(c, cur);
				p=link[p];
			}
			int q=nxt[p].get(c);
			
			// a node containing an edge with character c stopped me and it is not the root
			if(q!=cur){
				if(len[q]==len[p]+1)
					link[cur]=q;
				else{
					int clone=++idx;
					len[clone]=len[p]+1;
					link[clone]=link[q];
					nxt[clone]=new TreeMap<Character, Integer>(nxt[q]);
					link[cur]=link[q]=clone;
					while(nxt[p].get(c)==q){
						nxt[p].put(c, clone);
						p=link[p];
					}
				}
			}
			len[cur]=len[lst]+1;
			nxt[cur]=new TreeMap<Character, Integer>();
			lst=cur;
		}
		
	}
	
	static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {while (st == null || !st.hasMoreElements()) {
			try {st = new StringTokenizer(br.readLine());}
			catch (IOException e) {e.printStackTrace();}}
		return st.nextToken();}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() {return Double.parseDouble(next());}
		String nextLine(){String str = "";
		try {str = br.readLine();}
		catch (IOException e) {e.printStackTrace();}
		return str;}
	}
}