Palindromic Subsequences of Length 5

Problem Statement

Palindromic Subsequences of Length 5 Problem Description You are given a string s made up only of the characters '0' and '1' . A subsequence of s is obtained by deleting zero or more characters from s without changing the relative order of the characters that remain. A palindrome is a sequence that reads the same forwards and backwards. Count how many subsequences of s have length exactly 5 and are palindromes. Two subsequences are considered different whenever the set of positions used to build them is different , even if the two subsequences spell the very same string. So a subsequence of length 5 is identified by a tuple of indices i1 < i2 < i3 < i4 < i5 , and it is a palindrome exactly when s[i1] == s[i5] and s[i2] == s[i4] (the middle character s[i3] may be anything). Because the count can be enormous, report it modulo 10^9 + 7 . Function Description Complete the function getPalindromesCount with the following parameter: string s : the binary string