Unique Ab Strings

You are given a string s of "a" and "b"s. "a"s can stay "a" or turn into "b", but "b"s can’t change.

Return the number of unique strings that can be made.

Constraints

• 1 ≤ n ≤ 10,000 where n is the length of s

https://binarysearch.com/problems/Unique-Ab-Strings

Examples

Example 1

Input

• s = abba

Output

• answer = 4

Explanation

We can make these strings:

• "abba"
• "abbb"
• "bbba"
• "bbbb"

Solution