Python syntax

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.

1. 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.
2. 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.

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.

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

The string fefe has these two indentations.

for statement
    execute statement
for statement
    execute statement

for statement
    execute statement
    for statement
        execute statement