Russell can't wait to know Poland. As he waits he decided to learn a little of the Polish Language. To do this in a funny way he intends to use an old Polish dictionary and play a game he learned from the old Carl.

Given a word s in the dictionary, Russell is interested in sequences of suffixes of s. But not just any one! Russell considers amusing sequences of suffixes with the following properties:

• The suffixes appear in increasing sizes.
• The suffixes appear in lexicographic order.

As an example, if s = ABACA then the sequences (ABACA), (A, CA) and (A, ACA, BACA) please Russell but (ABACA, ACA) or (CA, ACA) doesn't.

Help Russell find the number of amusing sequences of suffixes of a given word s modulo 1000000007 (10^9 + 7).

Input

The input consists of several test cases. Each test case consists of only one line containing a string S with 1 to 100000 (10^5) uppercase latin letters (A - Z).

Output

For each test case output a single line containing the number of amusing sequences of suffixes of S modulo 1000000007 (10^9 + 7).

Example

Input:
ABACA
NIE
PIJ
WODY
CAMPINAS
Output:
11
7
5
8
20