Only Trivedi will survive !
Tag(s):

## Hard

Problem
Editorial
Analytics

Gaitonde wants to help Trivedi to survive. He know that Trivedi is not that much intelligent. Agents are using all their resources and manpower to try and locate Trivedi. Help him to survive by solving the problem.You are given a string $S$ consisting of only characters $a$ and $b$. In one step, you need to apply the following operation.

• Select any index $i$ such that $S[i]$ equals to $b$ and any of its adjacent characters is equal to $a$.
• Convert $S[i]$ to $a$.

Your task is to determine the number of ways to convert all the characters of string $S$ to $a$.

Input format:

• The first line consist of $T$ denoting the number of testcases.
• First line of each testcase consist of a single integer $N$.
• Second line of each testcase consist of a string $S$.

Output format:

• For each testcase, print the number of distinct ways to convert all the characters to $a$ (modulo 1000000007) in a new line.

Constraints :

• $1 \le T \le 100$
• $1 \le N \le 1000$

Note: It is guaranteed that atleast 1 character of the string $S$ is $a$

SAMPLE INPUT
2
4
abba
3
aaa
SAMPLE OUTPUT
2
1

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: Bash, 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, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

EPIPHANY 8.0

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > String Algorithms
• Algorithms > Dynamic Programming
Уведомления

?