Sorted Subsequences

Given a string A of string N consisting of lowercase characters only. Return the count of sub sequence of the given string in which the character are lexicographically sorted.

Empty subsequences are not counted in the answer.


ans (mod (10^9 + 7))

Constraints :
1 \leq N \leq 10^5

Input :
String A

Output :

Return an integer denoting the count of lexicographically sorted sub-sequences in the string.

Example :

A = “aba”

Output :

Explanation :
Every single character in the string {a, b, a} is a sorted subsequence of the string. So, count = 3.
“ab” and “aa” are sorted subsequences of length 2 of the given string. Count becomes 5.
There is no sorted subsequence of lenth 3.
So, total count = 5.