Distinct Palindromic Subsequences

A DNA strand is a string made of the letters A, C, G and T. A subsequence keeps some of its letters in their original order and drops the rest, and a palindrome reads the same forwards and backwards.

Write count_palindromes(strand) that returns how many different non-empty palindromic subsequences the strand has. Subsequences that spell the same string count once, however many ways there are to pick them. The count grows very quickly, so return it modulo 1,000,000,007 (the remainder after dividing by 10**9 + 7).

Examples

count_palindromes("ACCA")     # returns 6
count_palindromes("TTT")      # returns 3
count_palindromes("GATTACA")  # returns 10

The six palindromes in "ACCA" are A, C, AA, CC, ACA and ACCA.

Constraints

• 1 <= len(strand) <= 500
• strand holds only the letters A, C, G and T.