Consider a simplified programming language with two types of statements: for statements and simple statements. The rules of this language require that for statements are always followed by a statement with one additional unit of indentation, while simple statements are followed by statements with no additional indentation (and possibly less). Given a program as a list of statements with known types, you need to devise an algorithm which counts the number of different syntactically valid ways that the program could be indented. Two ways are considered different if there exists a statement with a different amount of indentation in each way.

For example, the program [for,simple,for,simple] can be indented in the following two ways:

for statement

simple statement

for statement

simple statement

OR

for statement

simple statement

for statement

simple statement

Analyze the runtime and memory requirements of your algorithm. Full marks will be given for a solution that uses O(n^3) time and O(n^2) memory, where n is the number of statements in the program (note that it is possible to solve the problem with event less time and space). Note: for the purposes of this problem you may assume that basic arithmetic operations such as addition always cost O(1) regardless of how large the values get. You may also assume that the program always ends with a simple statement.