<p>Given a string of digits <code>s</code>, return <em>the number of <strong>palindromic subsequences</strong> of</em> <code>s</code><em> having length </em><code>5</code>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p><strong>Note:</strong></p>

<ul>
	<li>A string is <strong>palindromic</strong> if it reads the same forward and backward.</li>
	<li>A <strong>subsequence</strong> is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;103301&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
There are 6 possible subsequences of length 5: &quot;10330&quot;,&quot;10331&quot;,&quot;10301&quot;,&quot;10301&quot;,&quot;13301&quot;,&quot;03301&quot;. 
Two of them (both equal to &quot;10301&quot;) are palindromic.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;0000000&quot;
<strong>Output:</strong> 21
<strong>Explanation:</strong> All 21 subsequences are &quot;00000&quot;, which is palindromic.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;9999900000&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> The only two palindromic subsequences are &quot;99999&quot; and &quot;00000&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>
	<li><code>s</code> consists of digits.</li>
</ul>

class Solution:
    def countPalindromes(self, s: str) -> int:
        modulo = 10**9+7

        # palindrome of length n:
        # the number is 2^(n/2)
        # we can track depth, and step through each number
        # 
        # find number of pairs of matching numbers with at least one element in between
        # brute force would be to look at all 5 letter sequences and returning the answer
        # however, we can't do that. So how would we know the answer? if we knew the number of pairs of matching
        # numbers, but that would take n^2
        
        # the key is that we are looking at digits instead of letters
        # there are a limited number of subsequences
        # literally only 10*10*10 = 1000 different subsequences
        # could we use this limiting number of subsequences to get the answer?
        # i.e. look for numbers between 00 and 99
        # could we search specifically for each palindrome?

        # if we count the number of digits to get number before i
        # then count number after i
        # track the number of halves that appear
        # track for each i, the number of two digit combos ending at it

        # maybe track i, t where t is two digit number. We have everything before and everything after and then multiply
        # what about the third number? 
        # number of two digits before i, number two digits after i (for each two digit number)
        # then cycle through each i as the middle and then add up the number combos on both sides

        # track # of each digit 0-9 before i.
        # number two digit numbers XY before i is going to be dp[X, i-1] + dp[XY,i-1]
        # (you add number of XYs before current plus all the XYs ending with current as Y)

        dpf = defaultdict(int)
        dpb = defaultdict(int)
        countsf = defaultdict(int) # current count of each str so far
        countsb = defaultdict(int)
        # go forward
        for i in range(len(s)):
            # s[i] is Y
            for j in range(10):
                dpf[str(j)+s[i], i] = countsf[str(j)] + dpf[str(j)+s[i], i-1]
                # carry over any previous strings
                for k in range(10):
                    if str(k) != s[i]:
                        dpf[str(j)+str(k), i] = dpf[str(j)+str(k), i-1]
            countsf[s[i]] += 1
            
        # go backward
        for i in range(len(s)-1,-1,-1):
            # s[i] is X
            for j in range(10):
                dpb[s[i]+str(j), i] = countsb[str(j)] + dpb[s[i]+str(j), i+1]
                # carry over any previous strings
                for k in range(10):
                    if str(k) != s[i]:
                        dpb[str(k)+str(j), i] = dpb[str(k)+str(j), i+1]
            countsb[s[i]] += 1
        
        total = 0
        strs = {str(i) + str(j) for i in range(10) for j in range(10) }
        for i in range(2,len(s)-2):
            for j in strs:
                total += dpf[j,i-1]*dpb[j[::-1],i+1]
                total %= modulo

        return total
397000