Problem Statement

Palindromic Subsequences You are given a string s made up solely of the characters '0' and '1' . Count how many length-5 subsequences of s are palindromes . Because the total can grow very large, report it modulo 10^9 + 7 . Definitions A palindrome is a sequence that reads the same backward as forward. A subsequence is obtained from the given sequence by deleting zero or more characters without changing the order of the remaining ones. The characters need not be adjacent. Two subsequences are considered different if the indices used to form them are different , even when the two selections spell the same string. Input Format A single line containing the binary string s . Output Format Print a single integer — the number of length-5 palindromic subsequences of s , modulo 10^9 + 7 . Constraints 5 <= length of s <= 10^5 Every character of s is either '0' or '1' . Examples Example 1 Input: 0100110 Output: 5 Explanation: using 1-based indices, the five qualifying selections are (1, 2,