Count Palindromic Subsequences
Given a string of digits s, return the number of palindromic subsequences of s having length 5. Since the answer may be very large, return it modulo 10^9 + 7.
Note:
- A string is palindromic if it reads the same forward and backward.
- A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
Example 1
Input
s = "103301"Output
2There are 6 possible subsequences of length 5, and two of them, both equal to "10301", are palindromic.
Example 2
Input
s = "0000000"Output
21All 21 subsequences are "00000", which is palindromic.
Constraints
- 1 <= s.length <= 10^4
- s consists of digits.