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++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic

Initializing Code Editor...

{"6c3a424": "/pagelets/recommended-problems/algorithm/favorite-subsequence/", "711156e": "/pagelets/show-submission/algorithm/favorite-subsequence/", "7da39d9": "/pagelets/suggested-problems/algorithm/favorite-subsequence/", "84fec35": "/pagelets/problems-hint/algorithm/favorite-subsequence/", "e2dc6a2": "/pagelets/problem-author-tester/algorithm/favorite-subsequence/"}

realtime.hackerearth.com

80

fe9b312d0306ce5faf709436a7f7c2e0b08eaf53

58a29e5cae2309f04b28

/realtime/pusher/auth/