A regular expression is used to describe a set of strings. For this problem the alphabet is limited to 'a' and 'b'.

We define to be a valid regular expression if:
1) is "" or "".
2) is of the form "", where and are regular expressions.
3) is of the form "" where and are regular expressions.
4) is of the form "" where is a regular expression.

Regular expressions can be nested and will always have have two elements in the parentheses. ('' is an element, '' is not; basically, there will always be pairwise evaluation) Additionally, '' will always be the second element; '' is invalid.

The set of strings recognized by are as follows:
1) If is "", then the set of strings recognized .
2) If is "", then the set of strings recognized .
3) If is of the form "" then the set of strings recognized = all strings which can be obtained by a concatenation of strings and , where is recognized by and by .
4) If is of the form "" then the set of strings recognized = union of the set of strings recognized by and .
5) If is of the form "" then the the strings recognized are the empty string and the concatenation of an arbitrary number of copies of any string recognized by .

Task
Given a regular expression and an integer, , count how many strings of length are recognized by it.