As we all known, xiaoxin is a brilliant coder. He knew **palindromic** strings when he was only a six grade student at elementry school.
This summer he was working at Tencent as an intern. One day his leader came to ask xiaoxin for help. His leader gave him a string and he wanted xiaoxin to generate palindromic strings for him. Once xiaoxin generates a different palindromic string, his leader will give him a watermelon candy. The problem is how many candies xiaoxin's leader needs to buy?
Input
This problem has multi test cases. First line contains a single integer $T(T\leq 20)$ which represents the number of test cases.
For each test case, there is a single line containing a string $S(1 \leq length(S) \leq 1,000)$.
Output
For each test case, print an integer which is the number of watermelon candies xiaoxin's leader needs to buy after mod $1,000,000,007$.
