Windy's ABC

Time Limit: 5000MS

Memory Limit: 65536K

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

Hint

Source

POJ Monthly Contest – 2009.04.05, windy792677

提交代码