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.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class SuffixAutomaton {
	// 2 3 7 4 6 5
	final int MAXLEN;
	State st[];
	int sz, last;
	
	static class State {
		int len, link;
		boolean finalState;
		TreeMap<Character, Integer> next;
		public State() { next = new TreeMap<Character, Integer>(); }
	}
	
	public SuffixAutomaton(int maxLen) {
		MAXLEN = maxLen;
		st = new State[MAXLEN << 1];
		for(int i = 0; i < st.length; ++i) st[i] = new State();
		last = 0; st[0].len = 0; st[0].link = -1; sz = 1;
	}
	
	void add(char c) {
		int cur = sz++;
		st[cur].len = st[last].len + 1;
		int p;
		for (p = last; p != -1 && !st[p].next.containsKey(c); p = st[p].link)
	        st[p].next.put(c, cur);
		if (p == -1)
			st[cur].link = 0;
		else
		{
			int q = st[p].next.get(c);
			if(st[p].len + 1 == st[q].len)
				st[cur].link = q;
			else
			{
				int clone = sz++;
				st[clone].len = st[p].len + 1;
	            st[clone].next = new TreeMap<Character, Integer>(st[q].next);
	            st[clone].link = st[q].link;
	            for (; p!=-1 && st[p].next.get(c) == q; p=st[p].link)
	                st[p].next.put(c, clone);
	            st[q].link = st[cur].link = clone;
			}
		}
		last = cur;
	}
	
	static long memo[];
	static SuffixAutomaton sa;
	
	static long dp(int u)
	{
		
		if(memo[u] != 0) return memo[u];
		long paths = sa.st[u].finalState?1:0;
		for(Entry<Character, Integer> v : sa.st[u].next.entrySet())
			paths += dp(v.getValue());
		
		return memo[u] = paths;
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		char s[] = sc.nextLine().toCharArray();
		sa = new SuffixAutomaton(s.length);
		for(char c : s) sa.add(c);
		int cur = sa.last;
		while(cur > 0)
		{
			sa.st[cur].finalState = true;
			cur = sa.st[cur].link;
		}
		memo = new long[s.length << 1];
		dp(0);
		long ans = 0;
		for(int i = 1; i < sa.sz; ++i)
		{
			long size = sa.st[i].len - sa.st[sa.st[i].link].len;
			ans += size * (memo[i] * (memo[i] + 1) >> 1);
		}
		out.println(ans);
		
		out.flush();
	}
	
	static class Scanner{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public Scanner(FileReader r){	br = new BufferedReader(r);}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}

		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}

		public double nextDouble() throws IOException { return Double.parseDouble(next()); }

		public boolean ready() throws IOException {return br.ready();}
	}
}