SOLVE

LATER

Favorite Subsequence

Problem

Editorial

Analytics

You are given a String $$S$$ of length $$N$$.

Now, a good subsequence is one that can be represented in the form $$a^{i}b^{j}c^{k}$$, where $$ i \ge 1$$, $$ j \ge 1$$ and $$k \ge 1 $$. For example ,if $$i=2$$,$$j=1$$,$$k=3$$, it represents the string $$aabccc$$. In short, a good subsequence is a subsequence that first consist of $$i$$ $$'a'$$ characters, followed by $$j$$ $$'b'$$ characters, followed by $$k$$ $$'c'$$ characters, where $$ i \ge 1$$, $$ j \ge 1$$ and $$ k \ge 1 $$

Now, you need to find the number of good subsequences of String $$S$$. As the number of such subsequences could be rather large, print the answer **Modulo** $$10^9+7$$.

**Note1:** Two subsequences are considered different if the set of array indexes picked for the $$2$$ subsequences are different.

**Input Format**:

The first and only line of input contains the $$S$$

**Output Format** :

Print the required answer on a single line.

**Constraints**:

$$ 1 \le | S | \le 10^5 $$

Explanation

Valid sub sequences are(1-based indexing):

{1,2,3}

{1,2,6}

{1,5,6}

{4,5,6}

{1,2,5,6}

{1,4,5,6}

{1,2,3,6}

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

{"196d8b5": "/pagelets/show-submission/algorithm/favorite-subsequence/", "196d8f0": "/pagelets/problem-author-tester/algorithm/favorite-subsequence/", "196d906": "/pagelets/problems-hint/algorithm/favorite-subsequence/", "196d8d9": "/pagelets/suggested-problems/algorithm/favorite-subsequence/", "196d91a": "/pagelets/recommended-problems/algorithm/favorite-subsequence/"}

{}

realtime.hackerearth.com

80

fe9b312d0306ce5faf709436a7f7c2e0b08eaf53

58a29e5cae2309f04b28

/realtime/pusher/auth/