Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Block Ordering

Input: Standard Input (stdin)
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.

Input

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

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).

Constraints

For all subtasks:

  • 1 \leq N \leq 1,000

Subtasks

  • 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

Explanation

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

    2
    
  • Sample Input 2

    4
    r
    o
    a
    r
    

    Sample Output 2

    6