#描述#
月光闲来无事常常在掷硬币，以至于每次要做什么事的时候都要等掷硬币掷成的序列出现某一个他心中所想的序列才肯罢休。而有时候他会因为这耽误大事，所以他想计算出他心中的序列平均的情况下要掷多少次才会出现。H(HEAD)表示出现正面，T(TAIL)表示反面，则如果他心中所想是HH，则他第一次可能掷成H或T，第二次掷后出现HH,HT,TT,TH四种情况，而HH是符合要求，如果他掷到的是TH则下次他掷出的是H而使序列成为THH，这也是符合的。而如果掷的是THT则等于要从头来过了。经过长年的研究他终于找出计算期望掷的次数的方法。首先，对于串s，正整数i,定义p(s,i)为s的长为i的前缀,定义q(s,i)为s的长为i的后缀,设最低位为第0低位，则每个长n的串的期望对应于一个n+1位的二进制数如果p(s,i)等于q(s,i)则这个二进制数的第i低位上就为1，另外所有位为0。例如串THT对应于4位的二进制数,p(s,3)=q(s,3),p(s,1)=q(s,1)则期望为二进制数(1010) 。

#格式#
##输入格式##
先一行中有一个每个字符为H或T的字符串，串长小于100000

##输出格式##
每组数据输出一个整数,这个整数为结果模10007

#样例1#
##样例输入1##

HT
T

##样例输出1##

4
2

#限制#
1000ms
32768KB

#提示#

#来源#
DK