Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds
Bjarne has a collection of wooden blocks numbered from 1 to N and likes to play a game with them. He starts by lining all the blocks up in order. Then he assigns each block one of four rules:
- Acquire - No block after this one can be moved before this one
- Release - No block before this one can be moved after this one
- Sequential - The same as 'Acquire' and 'Release' combined (which means no block after this one can be moved before this one and vice versa)
- Relaxed - No constraints
Additionally, you are guaranteed that there will be at least one 'Sequential' block within every eight consecutive blocks. If the total number of blocks is less than eight, then there might not be any 'Sequential' block.
Given the rules for each block, Bjarne wants to know how many ways there are to order all the blocks while satisfying each rule.
The first line contains one integer, N, the number of blocks Bjarne has. The following N lines each contain one of four possible characters:
- 'a' if this block has the rule 'Acquire'
- 'r' if this block has the rule 'Release'
- 's' if this block has the rule 'Sequential'
- 'o' if this block has the rule 'Relaxed'
Output the number of ways to order all the blocks while satisfying each rule. As the result can be a very large number, print out the number of ways modulo 10^9 + 7 (the remainder of dividing by 10^9 + 7).
For all subtasks:
- 1 \leq N \leq 1,000
- Subtask 1 (+10%): 1 \leq N \leq 7 and every block is 'o' (Relaxed)
- Subtask 2 (+30%): 1 \leq N \leq 10
- Subtask 3 (+30%): Every block is either 'o' (Relaxed) or 's' (Sequential)
- Subtask 4 (+30%): No further constraints
In the first sample case there are 2 possible block orderings:
- 1 (s), 2 (o), 3 (a), 4 (r)
- 1 (s), 3 (a), 2 (o), 4 (r)
In the second sample case there are 6 possible block orderings:
- 1 (r), 2 (o), 3 (a), 4 (r)
- 2 (o), 1 (r), 3 (a), 4 (r)
- 2 (o), 3 (a), 1 (r), 4 (r)
- 3 (a), 2 (o), 1 (r), 4 (r)
- 1 (r), 3 (a), 2 (o), 4 (r)
- 3 (a), 1 (r), 2 (o), 4 (r)
Note: Python submissions should use Python 3.6 (PyPy 7.3), as submissions using Python 3.8 may not be fast enough to pass some subtasks.
Sample Input 1
4 s o a r
Sample Output 1
Sample Input 2
4 r o a r
Sample Output 2