In the period between Nov. 28, 00:00 (UTC) and Nov. 28, 02:30 (UTC) Codeforces and Polygon will be possibly unavailable because of maintenance.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Asterisk Substrings

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputConsider a string $$$s$$$ of $$$n$$$ lowercase English letters. Let $$$t_i$$$ be the string obtained by replacing the $$$i$$$-th character of $$$s$$$ with an asterisk character *. For example, when $$$s = \mathtt{abc}$$$, we have $$$t_1 = \tt{*bc}$$$, $$$t_2 = \tt{a*c}$$$, and $$$t_3 = \tt{ab*}$$$.

Given a string $$$s$$$, count the number of distinct strings of lowercase English letters and asterisks that occur as a substring of at least one string in the set $$$\{s, t_1, \ldots, t_n \}$$$. The empty string should be counted.

Note that *'s are just characters and do not play any special role as in, for example, regex matching.

Input

The only line contains a string $$$s$$$ of $$$n$$$ lowercase English letters ($$$1 \leq n \leq 10^5$$$).

Output

Print a single integer — the number of distinct strings of $$$s, t_1, \ldots, t_n$$$.

Example

Input

abc

Output

15

Note

For the sample case, the distinct substrings are (empty string), a, b, c, *, ab, a*, bc, b*, *b, *c, abc, ab*, a*c, *bc.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/28/2020 01:54:15 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|