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.awt.Point;
import java.io.*;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

public class Tests {
	static Scanner in = new Scanner();
	static PrintWriter out = new PrintWriter(System.out);
	static SuffixAutomaton sa;

	public static void main(String[] test) throws NumberFormatException, IOException {
		String s = in.next();
		sa = new SuffixAutomaton(s.toCharArray());
		end = new int[s.length() * 2];
		int cur = sa.lst;
		end[cur] = 1;
		while (cur != 0) {
			cur = sa.link[cur];
			end[cur] = 1;
		}
		memo = new long[2 * s.length()];
		Arrays.fill(memo, -1);
		long ans = 0L;
		for (int i = 0; i <= sa.idx; i++) {
			long min_l = sa.len[sa.link[i]];
			long max_l = sa.len[i];
			long number_sub_in_state = max_l - min_l;
			long paths_to_end = dfs(i);
			long sum = paths_to_end * (paths_to_end + 1) * 1L / 2;
			ans += (sum * number_sub_in_state * 1L);
		}

		out.println(ans);
		out.flush();
		out.close();
	}

	static long memo[];
	static int end[];

	static long dfs(int state) {
		if (memo[state] != -1) {
			return memo[state];
		}
		long ret = 0L;
		if (end[state] == 1) {
			ret++;
		}
		for (Integer u : sa.next[state].values()) {
			ret += dfs(u);
		}
		memo[state] = ret;
		return ret;
	}

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

		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 {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

	}

}