This question was asked in Infosys test (2022).
Wael has a sequence S. He found that the sub-sequences of S that are derived from S after deleting exactly two letters are considered as beautiful subsequences.
Given string S, your task is to find the number of different beautiful subsequences of S. Since the answer can be very large return it modulo 10^9 + 7.
Input Format:
The first line contains a string S, denoting the given sequence.
Constraints:
1 <= len(S) <= 10^6
Sample Input:
aa --> 1 (The only beautiful sub-sequence is empty sequence)
bccb --> 4 (we can get {bc,cb,cc,bb} so answer is 4)
bbbbbb --> 1 (the only possible sub-sequence is bbbb, so answer is 1)
