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:
//package round92;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;

public class D {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	public Integer[] doLarssonSadakane(final char[] str)
	{
		int n = str.length;
		final int[] g = new int[n+1];
		int[] b = new int[n+1];
		Integer[] v = new Integer[n+1];
		for(int i = 0;i < n+1;i++){
			v[i] = i;
			g[i] = i == n ? -1 : str[i];
		}
		b[0] = 0; b[n] = 0;
		
		Arrays.sort(v, new Comparator<Integer>(){
			public int compare(Integer a, Integer b){
				if(a == b)return -1;
				return g[a] - g[b];
			}
		});
		for(int h = 1;b[n] != n;h *= 2){
			final int u = h;
			Comparator<Integer> comp = new Comparator<Integer>(){
				public int compare(Integer a, Integer b){
					if(a == b)return -1;
					if(g[a] - g[b] != 0)return g[a] - g[b];
//					int x = a+u<g.length ? g[a+u] : 0;
//					int y = b+u<g.length ? g[b+u] : 0;
//					return x - y;
					return g[a+u] - g[b+u];
				}
			};
			Arrays.sort(v, comp);
			for(int i = 0;i < n;i++){
				b[i+1] = b[i] + (comp.compare(v[i], v[i+1]) < 0 ? 1 : 0);
			}
			for(int i = 0;i < n+1;i++)g[v[i]] = b[i];
		}
		return v;
	}
	
	void solve()
	{
		char[] str = ns(100000);
		Integer[] ls = doLarssonSadakane(str);
		int[] lcp = buildLCP(str, ls);
		int n = str.length;
		int[][] start = new int[n+2][3];
		long local = 0;
		long ret = 0;
		int p = 0;
		for(int i = 1;i <= n;i++){
//			if(lcp[i] > 0){
				local += lcp[i];
				if(lcp[i-1] > lcp[i]){
					while(p > 0){
						if(lcp[i] < start[p-1][0]){
							local -= (long)(i-1-start[p-1][2]+1) * (start[p-1][1] - start[p-1][0]+1);
							p--;
						}else if(lcp[i] <= start[p-1][1]){
							local -= (long)(i-1-start[p-1][2]+1) * (start[p-1][1] - (lcp[i]+1)+1);
							start[p-1][1] = lcp[i];
							break;
						}else{
							break;
						}
					}
				}else if(lcp[i-1] < lcp[i]){
					start[p][0] = lcp[i-1]+1;
					start[p][1] = lcp[i];
					start[p][2] = i;
					p++;
				}
				ret += local;
//			}
		}
		out.println(ret+(long)n*(n+1)/2);
	}
	
	int[] buildLCP(char[] str, Integer[] ls)
	{
		int n = str.length;
		int h = 0;
		int[] lcp = new int[n+1];
		int[] b = new int[n+1];
		for(int i = 0;i < n+1;i++)b[ls[i]] = i;
		for(int i = 0;i < n+1;i++){
			if(b[i] != 0){
				for(int j = ls[b[i]-1]; j+h<n && i+h<n && str[j+h] == str[i+h]; h++);
				lcp[b[i]] = h;
			}else{
				lcp[b[i]] = -1;
			}
			if(h > 0)h--;
		}
		return lcp;
	}
	
	void run() throws Exception
	{
		is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static int sumFenwick(int[] ft, int i)
	{
		int sum = 0;
		for(i++;i > 0;i -= i&-i)sum += ft[i];
		return sum;
	}
	
	public static void addFenwick(int[] ft, int i, int v)
	{
		int n = ft.length;
		for(i++;i < n;i += i&-i)ft[i] += v;
	}
	
	public static int findGFenwick(int[] ft, int v)
	{
		int i = 0;
		int n = ft.length;
		for(int b = Integer.highestOneBit(n);b != 0 && i < n;b >>= 1){
			if(i + b < n){
				int t = i + b;
				if(v >= ft[t]){
					i = t;
					v -= ft[t];
				}
			}
		}
		return v != 0 ? -(i+1) : i-1;
	}
	
	public static int sumRangeFenwick(int[] ft, int[] ftp, int i)
	{
		int n = ft.length;
		int sum = 0;
		for(i++;i > 0;i -= i&-i){
			sum += ft[i];
			int num = i&-i;
			for(int j=i+(i&-i);j < n;j += j&-j){
				sum += ftp[j]*num;
			}
		}
		return sum;
	}
	
	public static void addRangeFenwick(int[] ft, int[] ftp, int i, int v)
	{
		int n = ft.length;
		for(i++;i > 0;i -= i&-i){
			ftp[i] += v;
			int w = v*(i&-i);
			for(int j = i;j < n;j += j&-j){
				ft[j] += w;
			}
		}
	}
	
	public static void main(String[] args) throws Exception
	{
		new D().run();
	}
	
	public int ni()
	{
		try {
			int num = 0;
			boolean minus = false;
			while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
			if(num == '-'){
				num = 0;
				minus = true;
			}else{
				num -= '0';
			}
			
			while(true){
				int b = is.read();
				if(b >= '0' && b <= '9'){
					num = num * 10 + (b - '0');
				}else{
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}
	
	public long nl()
	{
		try {
			long num = 0;
			boolean minus = false;
			while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
			if(num == '-'){
				num = 0;
				minus = true;
			}else{
				num -= '0';
			}
			
			while(true){
				int b = is.read();
				if(b >= '0' && b <= '9'){
					num = num * 10 + (b - '0');
				}else{
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}
	
	public String ns()
	{
		try{
			int b = 0;
			StringBuilder sb = new StringBuilder();
			while((b = is.read()) != -1 && (b == '\r' || b == '\n' || b == ' '));
			if(b == -1)return "";
			sb.append((char)b);
			while(true){
				b = is.read();
				if(b == -1)return sb.toString();
				if(b == '\r' || b == '\n' || b == ' ')return sb.toString();
				sb.append((char)b);
			}
		} catch (IOException e) {
		}
		return "";
	}
	
	public char[] ns(int n)
	{
		char[] buf = new char[n];
		try{
			int b = 0, p = 0;
			while((b = is.read()) != -1 && (b == ' ' || b == '\r' || b == '\n'));
			if(b == -1)return null;
			buf[p++] = (char)b;
			while(p < n){
				b = is.read();
				if(b == -1 || b == ' ' || b == '\r' || b == '\n')break;
				buf[p++] = (char)b;
			}
			return Arrays.copyOf(buf, p);
		} catch (IOException e) {
		}
		return null;
	}
	
	
	double nd() { return Double.parseDouble(ns()); }
	boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}