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.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class String_
{
	public static void main(String[] args) throws IOException
	{
		Scanner sc = new Scanner(System.in);
		char[] arr = sc.next().toCharArray();
		
		SuffixAutomaton a = new SuffixAutomaton(arr);
		
		System.out.println(a.solve());
	}
	static class SuffixAutomaton {

		int[] link, len;
		TreeMap<Character, Integer>[] next;
		int lst, idx;
		
		SuffixAutomaton(char[] s)
		{
			int n = s.length;
			link = new int[n<<1];
			len = new int[n<<1];
			next = new TreeMap[n<<1];
			next[0] = new TreeMap<>();
			for(char c: s)
				addLetter(c);
		}
		
		void addLetter(char c)
		{
			int cur = ++idx, p = lst;
			while(!next[p].containsKey(c)) { next[p].put(c, cur); p = link[p]; }
			
			int q = next[p].get(c);
			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;
		}
		
		int[] cnt;
		boolean[] f;
		public long solve()
		{
			cnt = new int[link.length];
			f = new boolean[link.length];
			int cur = lst;
			while(cur > 0)
			{
				f[cur] = true;
				cur = link[cur];
			}
			
			dfs(0);
			
			long ans = 0;
			for (int i = 1; i < cnt.length; i++)
				ans += 1l*(len[i]-len[link[i]])*((1l*cnt[i]*(cnt[i]+1))/2);
			
			return ans;
		}
		
		void dfs(int u)
		{
			if(f[u])
				cnt[u]++;
			for (char c : next[u].keySet())
			{
				int v = next[u].get(c);
				if(cnt[v] == 0)
					dfs(v);
				cnt[u] += cnt[v];
			}
		}
	}
	
	static class Scanner 
	{
		StringTokenizer st; BufferedReader br;
		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
		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 boolean ready() throws IOException {return br.ready();}
	}
	
}