Palindrome Subsequences :
Difficulty Level : Hard
Submissions : 391
Asked In :
Marks :20
: 3 | : 0
Given a binary string $$$S$$$, find the number of subsequences of length 5 which are palindromes.
A palindrome is a string that reads the same backward as forward, for example strings "z","aaa","aba","abccba" are palindromes, but strings "algouniversity","reality","ab" are not.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first and only line of each testcase contains a binary string $$$S$$$ $$$(1 \le |S| \le 10^5)$$$.
It is guaranteed that the sum of $$$|S|$$$ over all testcases does not exceed $$$10^5$$$.
For each test case, print a single integer — the number of subsequences of $$$S$$$ length 5 which are palindromes. As the answer can be rather large, print it modulo $$$10^9 + 7$$$.
3010011011100100
5 0 1
In sample test case 1, following are the palindromic subsequences of length 5:
- indices(1,2,3,6,7) -> "01010"
- indices(1,2,3,5,7) -> "01010"
- indices(1,2,4,6,7) -> "01010"
- indices(1,2,4,5,7) -> "01010"
- indices(1,2,5,6,7) -> "01110"
In sample test case 2, subsequences of length 5 are not possible. Hence the output is 0.
