Description

找出所有[i，j]为回文串,[j+1，k]也为回文串的i*k乘积之和,输出结果%1e9+7.

1<=i<=j<k<=|S|

Format

Input

本题为多组数据

每行一个字符串，长度<=1e6

数据组数<=5

Samples

aaa
abc

14
8