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 Strings;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class String2 {


	
	static class SuffixAutomaton {

		int[] link, len;
		long[] ways;
		TreeMap<Character, Integer>[] next;
		int lst, idx;
		
		SuffixAutomaton(char[] s)
		{
			int n = s.length;
			link = new int[n<<1];
			len = new int[n<<1];
			ways = new long[n<<1];
			next = new TreeMap[n<<1];
			next[0] = new TreeMap<>();
			Arrays.fill(ways, -1);
			for(char c: s)
				addLetter(c);
		}
		long dfs(int idx) {
			if(ways[idx]!=-1)
				return ways[idx];
			long way =0;
			for (Map.Entry<Character, Integer> entry : next[idx].entrySet()) {
				Character c = entry.getKey();
				Integer x = entry.getValue();
				if(c=='$'&&idx!=0)
					way++;
				else {
					way+= dfs(x);
				}
			}
			return ways[idx]=way;
		}	
		void traverse() {
			dfs(0);
		}
		void addLetter(char c)
		{
			int cur = ++idx, p = lst;
			//Keep adding to the suffix links of the last a link to the new cur
			while(!next[p].containsKey(c)) { next[p].put(c, cur); p = link[p]; }
			//this is the case where i am say adding a unique letter 
			int q = next[p].get(c);
			//if i am not already done by checking that the last suffix link 
			//is actually pointing at me
			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];
					next[clone] = new TreeMap<>(next[q]);
					link[cur] = link[q] = clone;
					while(next[p].get(c) == q) { next[p].put(c, clone);	p = link[p]; }
				}
			len[cur] = len[lst] + 1;
			next[cur] = new TreeMap<>();
			lst = cur;
		}
	}


public static void main(String[] args) throws IOException{
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	String x = in.readLine()+"$";
	SuffixAutomaton sa = new SuffixAutomaton(x.toCharArray());
	sa.traverse();
	long ans = 0;

	for (int i = 0; i < sa.ways.length; i++) {
		long cur = sa.ways[i];
		ans+=(cur)*(cur+1)/2*(sa.len[i]-sa.len[sa.link[i]]);
	}
	System.out.println(ans);
}
}