Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Windy's ABC
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 659Accepted: 296

Description

Windy is a stupid boy who can only write ABC. Now he has written a string S which contains only ABC and wonder how many string is a good copy of S. A copy is a permutation of S and a copy is good if and only if the distance between the positions of every letter in S and the copy is in a certain range. The range of distance of letter A B C is RA, RB and RC.

Input

The first line of input is the number of test case.
The first line of each test case contains three integers, RA, RB and RC.
The second line contains string S.
There is a blank line before each test case.

0 ≤ RA, RB and RC ≤ 10^9
0 < The length of S ≤ 500

Output

For each test case output the answer on a single line. Since the answer may be very large, just output the answer modulo 20090305.

Sample Input

4

1 1 0
AB

1 1 0
ABBA

2 3 4
ABBBABACCBCAABCBBCCC

3 1 5
ABCCCBCABACAAAB

Sample Output

2
4
645716
6660

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator