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

public class String_123D {
	static SuffixAutomaton sa;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		sb.append(sc.next());
		int n = sb.length();
		sa = new SuffixAutomaton(sb.toString().toCharArray());
		accept = new boolean[n << 1];
		int cur = sa.lst;
		accept[cur] = true;
		while (cur != 0) {
			cur = sa.link[cur];
			accept[cur] = true;
		}
		memo = new long[n << 1];
		Arrays.fill(memo, -1);
		long ans = 0;
		for (int i = 0; i <= sa.idx; i++) {
			long min = sa.len[sa.link[i]];
			long max = sa.len[i];
			long dif = max - min;
			long distinct = solve(i);
			long x = 1l * distinct * (distinct + 1) / 2;
			ans += (1l * dif * x);
		}
		System.out.println(ans);
	}

	static long[] memo;
	static boolean[] accept;

	static long solve(int idx) {
		if (memo[idx] != -1)
			return memo[idx];
		long ret = 0;
		if (accept[idx])
			ret++;
		for (Entry<Character, Integer> entry : sa.next[idx].entrySet()) {
			int nxtNode = entry.getValue();
			ret += solve(nxtNode);
		}
		return memo[idx] = ret;
	}

	static class SuffixAutomaton {
		int[] link, len;
		TreeMap<Character, Integer>[] next;
		int lst, idx;

		@SuppressWarnings("unchecked")
		public 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);

		}

		private 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 I stopped failing before reaching the root
				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;
		}

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

		public Scanner(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(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 double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

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