Burger, French Fries, Soft Drink

Anna is a waitress at Om Burger, a popular fast-food restaurant in Indonesia. Her job is easier than at other restaurants because Om Burger has an automatic food machine.

Om Burger serves only one combo, called Paket Uenak, made of three items: one Burger (B), one French Fries (F), and one Soft Drink (S). Each customer writes on a card how many Paket Uenak packages they want and hands it to Anna, who feeds it into the machine.

For a card, the machine prepares that card's items one by one, but in no particular order. For a card ordering 2 packages it outputs some permutation of BBFFSS (for example BFSBFS, BBFSFS, ...). The machine handles cards one at a time and never starts the next card before finishing the current one.

One busy day, Anna feeds several cards into the machine at once instead of one by one. It still works, but its output is a single stream of items with no separator between cards, so Anna can no longer tell which items came from which card.

Anna does remember how many cards she inserted and their order, but not the number of packages written on each card.

For example, suppose two cards were inserted and the machine produced:

B B F S S F S F B B F S

• Arrangement 1: (B B F S S F)(S F B B F S) — the first customer ordered 2 packages and the second ordered 2 packages.
• Arrangement 2: (B B F S S F S F B)(B F S) — the first customer ordered 3 packages and the second ordered 1 package.

So this stream can be split among the two cards in 2 different ways.

Given the number of cards and the produced item stream, help Anna count how many valid arrangements are possible. A valid arrangement splits the stream into consecutive blocks, one per card in order, where each block contains an equal and positive number of B, F, and S.

Each line of input contains an integer N ($1 < N < 30$), the number of cards inserted, followed by a space and a string made of the characters B, F, and S (no spaces) giving the order in which the machine produced the items. The length of each string is less than 100. Input continues until end of file; process every line.

For each line of input, print the number of possible arrangements. If no valid arrangement exists, print Impossible.