
ZOJ Problem Set  3892
Keine is a teacher and recently she is preparing the test paper of the midterm test of mathematics. The main content is the vector operation. She has already made some formulas before. Those formulas are about the most common vector operations:
In Gensokyo, there is another amazing operation:
Unfortunately Keine forgot to add brackets before printing the test paper. What's worse is that she hasn't teached her students the priority of these four operations. So she thinks it's necessary to prepare all possible answers. Now she wants to know the number of available compuation sequences and requires your help.
You don't want to be CAVED, do you? Input
There are multiple cases. Output
For each case, please output the number of available computation sequences. It may be very large, so you must output the answer modulo 10^{9} + 7. Sample Input4 32*x x*x 1*x^x 1!x!2!b Sample Output1 0 2 5 HintThe five computation sequences of the 4th sample are listed below:
If we use permutations to represent computation sequences, then 132 and 312 will be regarded as the same (the 2nd sequence). ReferenceAuthor: ZHAO, Yueqi Source: ZOJ Monthly, September 2015 