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

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class C {
	static int INF = (int) 1e9;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		char[] s = (sc.next() + '$').toCharArray();
		SuffixAutomaton sa = new SuffixAutomaton(s);
		sa.dfs(0);
		long sum = 0;
		for (int i = 1; i < sa.len.length; i++) {
			sum += sa.occ[i] * (sa.occ[i] + 1) / 2 * (sa.len[i] - sa.len[sa.link[i]]);
		}
		out.println(sum);
		out.flush();
		out.close();
	}

	static class SuffixAutomaton {

		int[] link, len;
		long[] occ;
		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<>();
			occ = new long[n << 1];
			Arrays.fill(occ, -1);
			for (char c : s)
				addLetter(c);
		}

		void dfs(int u) {
			if (occ[u] != -1)
				return;
			occ[u] = 0;
			for (Entry<Character, Integer> e : next[u].entrySet()) {
				int v = e.getValue();
				char c = e.getKey();
				if (c == '$')
					occ[u]++;
				dfs(v);
				occ[u] += occ[v];
			}
		}

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

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

		public Scanner(FileReader fileReader) {
			br = new BufferedReader(fileReader);
		}

		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();
		}
	}
}