class Solution:
    def dfs(self, s,res,index,cur_string):
        if cur_string==cur_string[::-1]:
            res.add(cur_string)
        for i in range(index,len(s)):
            self.dfs(s, res,i+1,cur_string+s[i])
    def countPalindromicSubsequences(self, S):
        BIG_NUM = 10**9+7
        res = set()
        s = S
        self.dfs(s,res,0,"")
        return (len(list(res))-1)%BIG_NUM