ATOURISM - Adventure Tourism
English | Vietnamese |
There has been a growing interest in adventure tourism lately. However, organizing adventure tours is not an easy task. It requires very careful preparation with attention to specific details.
This tour has p young male and q female participants. In addition to the logistic and rescue team, the organizers also assign k more guides to join the tour. In the first stage of the tour, the road is quite narrow passing a cliff; the group will have to go in one line. To be able to help each other, a female participant has to go next to, i.e. before or after, a male participant or a guide. Furthermore, there must be at least one participant next to a guide. Given these constraints, there are several ways the group can form a line. Let’s denote B, G and M as a male participant, a female participant and a guide respectively. A line formation can be represented by a string of length (p+q+k) containing characters from the set (B, G, M). Two line formations are different if their string representations are different. For example, the group having 2 male, 2 female and a guide (p = q = 2, k = 1) has 24 different way to form a line as follows:
Index |
Group Line |
Index |
Group Line |
Index |
Group Line |
Index |
Group Line |
1 |
BBGGM |
7 |
BGMBG |
13 |
MGBBG |
19 |
GBGMB |
2 |
BBGMG |
8 |
BGMGB |
14 |
MGBGB |
20 |
GBMBG |
3 |
BGBGM |
9 |
BMGBG |
15 |
MGGBB |
21 |
GBMGB |
4 |
BGBMG |
10 |
BMGGB |
16 |
GBBGM |
22 |
GMBBG |
5 |
BGGBM |
11 |
MBGBG |
17 |
GBBMG |
23 |
GMBGB |
6 |
BGGMB |
12 |
MBGGB |
18 |
GBGBM |
24 |
GMGBB |
Given p, q, and k, let’s denote n as the number of different ways to form a line. Your task is to write a program to calculate the remainder of n divided by 10^{7}.
Input
The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.
For each data test, there is only one line containing three integers p, q and k (0 ≤ p, q ≤ 1 000, 0 ≤ k ≤ 10) separated by space.
Output
For each data test, write in one line the remainder of the number of different line formations divided by 10^{7}.
Example
Sample Input 1 2 2 1 Sample Output 24
hide comments
[Rampage] Blue.Mary:
2009-12-16 09:58:21
What a tight time limit! What a boring optimization I've ever used!!! |
Added by: | Duc |
Date: | 2009-01-04 |
Time limit: | 0.426s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | ACM Regional, Ho Chi Minh City 2008 |