Gao the string!

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

give you a string, please output the result of the following function mod 1000000007

n is the length of the string

f() is the function of fibonacci, f(0) = 0, f(1) = 1...

a[i] is the total number of times any prefix appear in the suffix s[i....n-1].

(the prefix means s[0...i] )

Input

multiple test cases.

each test case will give you a string consists of lowercase letters, the length of which is no more than 100000.

Output

ouput a number.

Sample Input

aa

Sample Output

3

Hint

样例解释如下:

对于

aa这个后缀,前缀a出现了两次,前缀aa出现了一次,总共三次

对于a这个后缀,前缀a出现了一次

所以答案是f(3) + f(1)

Source

wuyiqi

Manager

Information
Solved Number121
Submit Number351
Problem Tags
hashing
strings
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel