As a programming contest addict, Waybl is always happy to take part in various competitive programming contests. One day, he was competing at a regional contest of Inventing Crappy Problems Contest(ICPC). He tried really hard to solve a "geometry" task without success.
After the contest, he found that the problem statement is ambiguous! He immediately complained to jury. But problem setter, the Great Pan, told him "There are only four possibilities, why don't you just try all of them and get Accepted?".
Waybl was really shocked. It is the first time he learned that enumerating problem statement is as useful as trying to solve some ternary search problem by enumerating a subset of possible angle!
Three years later, while chatting with Ceybl, Waybl was told that some problem "setters" (yeah, other than the Great Pan) could even change the whole problem 30 minutes before the contest end! He was again shocked.
Now, for a given problem statement, Waybl wants to know how many ways there are to understand it.
A problem statement contains only newlines and printable ASCII characters (32 ≤ their ASCII code ≤ 127) except '{', '}', '|' and '$'.
Waybl has already marked all ambiguity in the following two formats:
1.{A|B|C|D|...} indicates this part could be understand as A or B or C or D or ....
2.$blah blah$ indicates this part is printed in proportional fonts, it is impossible to determine how many space characters there are.
Note that A, B, C, D won't be duplicate, but could be empty. (indicate evil problem setters addedclarified it later.)
Also note that N consecutive spaces lead to N+1 different ways of understanding, not 2N ways.
It is impossible to escape from "$$" and "{}" markups even with newlines. There won't be nested markups, i.e. something like "${A|B}$" or "{$A$|B}" or "{{A|B}|C}" is prohibited. All markups will be properly matched.