Description

记S(i,j)为字符串S的第i个字母到第j个字母组成的子串。

给出一个长度为n由小写英文字母组成的字符串A。

若字符串B也由小写英文字母组成，长度为n，且对于任意1<=i<j<=n有：若A(i,j)是回文串，B(i,j)也是回文串；若A(i,j)不是回文串，B(i,j)也不是回文串。那么我们称B与A是ayq相似的。

求有多少个字符串与A ayq相似？输出答案对1000000007取模的余数。

Format

Input

输入1行一个字符串A

Output

输出一行一个数表示所求答案

Samples

abcba

15600

Limitation

对于100%的数据，n<=1000000