Python syntax

Time limit1sMemory limit128 MB

Summary

Given a string of for and execute statements, count the valid Python indentation schemes modulo 1,000,000,007.

Level: Medium6 of 10
Topics: Dynamic programming, Implementation, Math, Combinatorics
Solved: No attempts yet

Problem

Unlike C or Java, the programming language Python does not separate code with opening and closing braces. It separates code by indentation (a tab) instead. This problem deals with only two Python statements.

for statement: a statement used for repetition, and it can contain several statements. Once a for statement begins, the statements it repeats must be indented one tab further than the for statement, and the block inside a for statement cannot be empty.
execute statement: a statement that performs an execution. You can write one per line.

Given several statements in order with no indentation, write a program that prints how many ways there are to indent them.

Input

The first line contains a string of $N$ ( $1 \le N \le 5000$ ) characters. Each character is 'f' (the for statement described above) or 'e' (the execute statement described above). No input is given for which every possible indentation breaks Python syntax.

Output

Print the number of indentations of the given statements that satisfy Python syntax, modulo 1,000,000,007.

Note

The string fefe has these two indentations.

for statement
    execute statement
for statement
    execute statement

for statement
    execute statement
    for statement
        execute statement

Examples1

Example 1
Input
```
fefe
```
Expected output
```
2
```