Have you ever seen a bee dancing? Maybe your answer is “no”, but little Johnny would say “Yes”.
After observing some dancing bees, little Johnny noticed that some of them only took forward and backward steps, and always returned to the starting point when stopped. He wrote down their moving steps as a dancing sequence on a piece of paper, and decided to use the character ‘F’ and ‘B’ to denote forward or backward steps respectively.
But little Johnny is a poor hand at writing. A week later when he came back to his notes, little Johnny found out that he had put some ambiguous ‘R’ instead of a clear ‘F’ or ‘B’ character. He could not even be sure that every single ‘R’ was a forward or a backward step. The only thing that he was sure was that each dancing bee started dancing at a corner of little Johnny’s desk, so none of these bees could not take too many backward steps to avoid falling of the desk.
Therefore little Johnny came to you. He knew that you are the only one who can solve his problem. The problem is to compute how many possible dancing sequences from his ambiguous note. Note that it would be a case if none of all dancing sequences satisfies the condition described above.
The input consists of multiple test cases. There is an integer T(1 ≤ T ≤ 20)
denoting the number of test cases. Each test case contains two lines, where the first line contains an integer n (2 ≤ n ≤ 2000) which denotes the lengthof a dancing sequence. The second line consists a string composed of ‘F’, ‘B’,
and ‘R’ of length n.
For each test case, print a line consisting the case number (beginning with 1) followed by an integer indicating the last nine digits of possible dancing sequences. Since the answer may be large, you should only output the last nine digits of the number if the number is not less than 1,000,000,000. Otherwise you should just print the number.
3 2 RR 4 FRBR 4 BRRR
Case 1: 1 Case 2: 1 Case 3: 0
Migrated from old NTUJ.
PTC 2009/03
| No. | Testdata Range | Score |
|---|