Mọi xâu kí tự đều có thể được ghép từ một số xâu đối xứng (palindrome). Ví dụ: acbcabca = acbca+b+c+a hoặc:

= a + cbc+a+b+c+a

Yêu cầu: Cho xâu kí tự S, hãy đếm số cách chia xâu S thành các xâu palindrome như trên.

Dữ liệu: gồm một dòng chứa xâu S (độ dài không quá 300).

Kết quả: Ghi ra một số là kết quả tìm được modulo cho 10^9+7.

Ví dụ:

Input

acbcabca

Output

3