countPalindromes

Một palindrome là một từ hoặc cụm từ hoặc một chuỗi các ký tự khác đọc ngược cũng giống như đọc xuôi, chẳng hạn như madam hoặc abcba hoặc số 13431.

Adam cảm thấy palindrome rất thú vị. Thay vì nghĩ về việc kiểm tra một xâu ký tự có phải là palindrome hay không, anh bắt đầu nghĩ về các cách có thể loại bỏ đi các chữ cái trong một xâu cụ thể để xâu đó có thể là một palindrome.

Cũng có trường hợp không thể bỏ chữ cái nào để tạo thành một palindrome.

Ví dụ

• Với S = pasta, đầu ra là countPalindromes(S) = 8
  Ta có 8 cách để loại bỏ các chữ cái để S thành một palindrome:
  1. 5 cách để bỏ 4 chữ cái {p, a, s, t} 
  2. Bỏ {p, s, t} để tạo thành xâu {aa}
  3. Bỏ {p, t} để tạo thành xâu {asa}
  4. Bỏ {p, s} để tạo thành xâu {ata}

Đầu vào/Đầu ra

• [giới hạn thời gian chạy] 1.5 giây

• [đầu vào] string S

  Điều kiện tiền đề:
  1 ≤ length(S) <= 1000.

• [đầu ra] long long

  Tổng số các cách để bỏ các chữ cái từ S sao cho nó thành một palindrome. Lấy phần dư của phép chia cho 1000000007 (109+7)