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.IOException;
import java.io.InputStreamReader;
//import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map.Entry;
import java.util.TreeMap;

public class SuffixAutomaton {

	static class State{
		
		int maxLen, suffixLink;
		boolean end;
		TreeMap<Character, Integer> next;
		
		public State(int maxLen){
			next = new TreeMap<>();
			this.maxLen = maxLen;
		}
		
		public State(int maxLen, int suffixLink){
			next = new TreeMap<>();
			this.maxLen = maxLen;
			this.suffixLink = suffixLink;
		}
		
	}
	
//	ArrayList<State> states;
//	ArrayList<Integer> endPos;
	State[] states;
	int[] endPos;
	long[] visited;
	int[] count;
	int size, last;
	
	public SuffixAutomaton(String s){
//		states = new ArrayList<>();
//		endPos = new ArrayList<>();// carries the first end pos of the node
		states = new State[2*s.length() + 1];
		endPos = new int[2*s.length() + 1];
		states[0] = new State(0, -1);
		size = last = 0;
		size++;
		build(s);
		markEndStates();
	}
	
	public void build(String s){
		for(int i = 0; i < s.length(); i++){
			insertCharacter(s.charAt(i), i);
		}
	}
	
	public void insertCharacter(char c, int i){
		// we need to set the node's 
		//		maxLen
		//		suffixLink
		// 		transitions	
		
		states[size] = new State(states[last].maxLen + 1);
//		states.add(newState);
		endPos[size] = i;
		int idx = size++;
		int p;
		for(p = last; p != -1 && !states[p].next.containsKey(c); p = states[p].suffixLink){
			states[p].next.put(c, idx);
		}
		if(p == -1){
			states[idx].suffixLink = 0;
		}else{
			// a split may be needed
			int q = states[p].next.get(c);
			if(states[p].maxLen + 1 == states[q].maxLen){
				// we don't need to split
				states[idx].suffixLink = q;
			}else{
				// we need to split
				int clone = size++;
				states[clone] = new State(states[p].maxLen + 1);
//				states.add(t);
				states[clone].next = new TreeMap<>(states[q].next);
				states[clone].suffixLink = states[q].suffixLink;
				endPos[clone]  = endPos[q];
				for(; p != -1 && states[p].next.get(c) == q; p = states[p].suffixLink){
					states[p].next.put(c, clone);
				}
				states[q].suffixLink = clone;
				states[idx].suffixLink = clone;
			}
		}
		last = idx;
	}
	
	public void markEndStates(){
		for(int i = last; i != -1; i = states[i].suffixLink){
			states[i].end = true;
		}
	}
	
	public long reachableEnds(int i){
//		System.out.println(i);
		if(visited[i] != -1)
			return visited[i];
		int c = 0;
		if(states[i].end)
			c++;
		for(Entry<Character, Integer> e: states[i].next.entrySet()){
			c += reachableEnds(e.getValue());
		}
		return visited[i] = c;
	}
	
//	public int countDistinct(){
//		int f = 0;
//		visited = new int[size];
//		count = new int[size];
//		Arrays.fill(visited, -1);
//		Arrays.fill(count, -1);
//		for(int i = 1; i < size; i++){
//			if(visited[i] == -1)
//				visited[i] = reachableEnds(i);
//			f += (states[i].maxLen - states[states[i].suffixLink].maxLen)*visited[i]*(visited[i] + 1) / 2;
//		}
//		return f;
//	}
	
	public String toString(){
		StringBuilder res = new StringBuilder();
		for(int i = 0; i < size; i++){
			res.append("node " + i + ":\n");
			State cur = states[i];
			res.append("\tsuffixLink: " + cur.suffixLink + "\n");
			res.append("\tend: " + cur.end + "\n");
			res.append("\tmaxLen: " + cur.maxLen + "\n");
			res.append("\tLinks: " + "\n");
			for(Entry<Character, Integer> e: cur.next.entrySet()){
				res.append(e.toString() + "\n");
			}
		}
		return res.toString();
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		String s = br.readLine();
		SuffixAutomaton auto = new SuffixAutomaton(br.readLine());
//		System.out.println(auto.countDistinct());

		auto.visited = new long[auto.size];
		Arrays.fill(auto.visited, -1);
		auto.reachableEnds(0);
//		System.out.println(auto.reachableEnds(0));
//		System.out.println(Arrays.toString(auto.visited));
		long f = 0;
		for(int i = 1; i < auto.size; i++){
//			if(auto.visited[i] == -1)
//				auto.visited[i] = auto.reachableEnds(i);
			f += (auto.states[i].maxLen - auto.states[auto.states[i].suffixLink].maxLen)*auto.visited[i]*(auto.visited[i] + 1) / 2;
		}
		System.out.println(f);
	}
	
}