题目描述

在数学中，子序可以从另一个序列中删除某些元素而不改变其余元素的顺序得到。例如，<A, B, D>序列是<A, B, C, D, E, F>的子序列。

给定一个字符串$S$，你的任务是找出S有多少个不同的子序列是回文。注意，对于任意两个子序列$X = S_{x1}, S_{x2}，…， S_{yk}$，如果存在一个整数 $i$ ($1<=i<=k$) 使$x_i != y_i$，那么即使$S_{xi} = S{yi}$，子序列$X$和$Y$也应该被认为不同。同样，两个长度不同的子序列也应该被认为是不同的。

输入格式

包含一个字符串S，S的长度不大于1000，并且只包含小写字母。

输出格式

输出给定字符串的不同子序列的数量，答案取模10007

样例

输入

a

1

aaaaa

输出

31