Now safely in space, you decide to take a break for a bit. You go to the rec room to play a nice game of solitaire. However, you realize that all the heart cards are missing! And the face cards! And the aces! And the 9 and 10 cards, for some reason. Strange.

Anyways, you can't play solitaire with 21 cards, so you quickly make up a game on the spot:

Initially, all 7 spade cards are laid in a row from 2 to 8.

You give yourself N turns. Each turn, you either:
1. Replace a card with another card of a different suit but same value (e.g. you can replace the 7 of clubs with the 7 of diamonds or the 7 of spades, but not the 5 of clubs)
2. Find two adjacent cards of different suits and swap their suits (e.g. if the 7 of clubs and 8 of spades are next to each other, you can replace them with the 7 of spades and 8 of clubs, respectively)

You wonder how many ways there are to reach a given configuration given ~N~ turns. More formally, you want to know how many unique move sequences of length ~N~ there are that transform a sequence of all spades to a specific sequence of suits. Two sequences of moves are unique if, after some fixed number of turns, their configurations are different.

Because this number may be very large, you'll settle for finding the answer modulo ~10^9 + 7~.

Constraints

Subtask 1 [20%]

~1 \leq N \leq 2~

Subtask 2 [80%]

~1 \leq N \leq 10^3~

Input Specification

The first line will contain ~N~, the number of moves you will do.

The next line will contain one 7-character-long string, representing the target configuration you want to reach. Each character is a string which is either S, D, or C, representing Spades, Diamonds, or Clubs respectively.

Output Specification

The first and only line of output should contain one integer, the number of ways to reach the target configuration modulo ~10^9 + 7~.

Sample Input 1

2
DSSSSSS

Sample Output 1

2

Sample Explanation

There are two ways to reach this configuration in exactly 2 turns:

1. Replace the first card with Clubs, then replace it again with Diamonds
2. Replace the second card with Diamonds, then swap the suits of the first and second cards