ATOURISM - Adventure Tourism

no tags 

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 107.

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 107.

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