Trong một hệ thống truyền tin bảo mật, các thông điệp được mã hóa dưới dạng một xâu ký tự ~S~. Một thông điệp được coi là "hợp lệ" nếu nó có thể được chia cắt thành một hoặc nhiều phần liên tiếp, mà mỗi phần đều là một xâu đối xứng (đọc xuôi hay đọc ngược đều giống nhau).

Các chuyên gia mật mã muốn đánh giá độ phức tạp của một bản tin bằng cách xác định xem có bao nhiêu cách khác nhau để phân chia bản tin đó thành các phân đoạn đối xứng. Hai cách chia được coi là khác nhau nếu vị trí các điểm cắt để phân tách các xâu con là khác nhau.

Yêu cầu: Cho xâu ký tự ~S~. Hãy tính tổng số cách phân chia xâu ~S~ thành các xâu con sao cho mỗi xâu con đều là xâu đối xứng. Vì kết quả có thể rất lớn, hãy đưa ra đáp số sau khi chia lấy dư cho ~10^9+7~.

Input

Một dòng duy nhất chứa xâu ký tự ~S~ ~(1 < |S| \le 2000)~, chỉ gồm các chữ cái Latin in thường.

Output

Một số nguyên duy nhất là số cách phân chia tìm được theo modulo ~10^9+7~.

Sample Input 1

aba

Sample Output 1

2

Notes

Với xâu ~S =~ "aba", có ~2~ cách phân chia hợp lệ:

• Chia thành ~3~ xâu con: ~\{~"a", "b", "a"~\}~ (tất cả đều là xâu đối xứng đơn lẻ).

• Giữ nguyên thành ~1~ xâu con: ~\{~"aba"~\}~ (bản thân "aba" là xâu đối xứng).

Lưu ý: Cách chia ~\{~"ab", "a"~\}~ không hợp lệ vì "ab" không đối xứng.