POLISH - Polish Language

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

Added by:Paulo Costa
Date:2012-01-17
Time limit:0.801s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IME/USP 1 - Brazilian ICPC Training Camp, Jan-Feb/2012

hide comments
2012-02-09 14:55:44 Equipe Up (Cesar, Leonardo e Lucas)
Statement and input data updated!
Read the input as you want! Problems fixed!
There will be only one word in each line and no character which is not a latin uppercase letter('A'-'Z') or end of line('\n') in the input.
2012-02-09 14:47:18 Andrés Mejía-Posada
Looks like the input file has several word on the same line. Make sure your program can handle two different words on the same line separated by spaces (for example, use "cin >> s"). I was getting Wrong Answer until I changed this.
2012-02-09 14:47:18 Equipe Up (Cesar, Leonardo e Lucas)
S will have at least one character!
There will be no empty strings!
You can read with 'scanf("%s")' or 'cin'... Please don't read with 'gets' or something similar, there is a whitespace in the end of one of the input lines. We are going to fix this as soon as possible. Sorry!

Last edit: 2012-02-09 14:40:53
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.