버거, 감자튀김, 음료수

안나(Anna)는 인도네시아의 인기 패스트푸드점 Om Burger에서 일하는 종업원입니다. Om Burger에는 자동 조리 기계가 있어서 다른 가게보다 일이 훨씬 수월합니다.

Om Burger는 Paket Uenak이라는 세트 메뉴 하나만 판매합니다. 이 세트는 버거(B) 1개, 감자튀김(F) 1개, 음료수(S) 1개로 구성됩니다. 손님은 주문할 Paket Uenak 세트의 개수를 카드에 적어 안나에게 건네고, 안나는 그 카드를 기계에 넣습니다.

기계는 카드 한 장에 적힌 개수만큼 항목을 하나씩 만들어 내는데, 순서는 정해져 있지 않습니다. 예를 들어 어떤 카드에 2가 적혀 있으면 기계는 BBFFSS의 어떤 순열(예: BFSBFS, BBFSFS 등)이든 만들어 낼 수 있습니다. 기계는 카드를 한 장씩 순서대로 처리하며, 현재 카드를 다 끝내기 전에는 다음 카드로 넘어가지 않습니다.

어느 바쁜 날, 안나는 카드를 한 장씩 넣는 대신 여러 장을 한꺼번에 넣었습니다. 기계는 정상적으로 작동했지만, 카드 사이에 아무런 구분 표시 없이 항목들을 하나의 연속된 열로 만들어 냈기 때문에 어떤 항목이 어떤 카드에서 나온 것인지 알 수 없게 되었습니다.

안나는 넣은 카드의 개수와 그 순서는 기억하지만, 각 카드에 적힌 세트 개수는 기억하지 못합니다.

예를 들어 카드 두 장을 넣어 기계가 다음과 같은 열을 만들어 냈다고 합시다.

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

• 배열 1: (B B F S S F)(S F B B F S) — 첫 번째 손님이 2세트, 두 번째 손님이 2세트를 주문한 경우.
• 배열 2: (B B F S S F S F B)(B F S) — 첫 번째 손님이 3세트, 두 번째 손님이 1세트를 주문한 경우.

따라서 이 열을 두 카드로 나누는 방법은 2가지입니다.

카드의 개수와 기계가 만들어 낸 항목 열이 주어질 때, 가능한 배열의 수를 세어 안나를 도와주세요. 올바른 배열이란 이 열을 카드 순서대로 연속된 구간으로 나눈 것으로, 각 구간에 B, F, S가 같은 개수만큼(1개 이상) 들어 있어야 합니다.

입력의 각 줄에는 넣은 카드의 개수를 나타내는 정수 N ($1 < N < 30$)과, 기계가 항목을 만들어 낸 순서를 나타내는 문자열이 공백으로 구분되어 주어집니다. 이 문자열은 B, F, S 문자로만 이루어져 있으며 공백을 포함하지 않습니다. 각 문자열의 길이는 100 미만입니다. 입력은 파일의 끝까지 계속되며, 모든 줄을 처리해야 합니다.

각 줄마다 가능한 배열의 수를 출력합니다. 올바른 배열이 하나도 없으면 Impossible을 출력합니다.