ATOURISM - Adventure Tourism

Các tour du lịch mạo hiểm ngày càng thu hút được sự quan tâm của các bạn trẻ. Tuy vậy, tổ chức du lịch mạo hiểm là cả một vấn đề. Nó đòi hỏi ban tổ chức phải chu đáo, tỷ mỷ đến tận từng chi tiết nhỏ nhất trong khâu chuẩn bị.

Tour du lịch kỳ này có p du khách nam và q du khách nữ tham gia. Ngoài lực lượng hậu cần và ứng cứu khẩn cấp, ban tổ chức còn phân công thêm k hướng dẫn viên đi với đoàn. Ở chặng thứ nhất đường đi khá hẹp và cheo leo, cả đoàn phải đi thành hàng một. Để có thể trợ giúp nhau, quy tắc hình thành đoàn đi là cạnh một du khách nữ phải có một du khách nam hay một hướng dẫn viên (đi trước hoặc đi sau), cạnh một hướng dẫn viên phải có ít nhất một du khách. Có nhiều cách tổ chức đoàn thành hàng đi. Ký hiệu B là du khách nam, G là du khách nữ, và M là hướng dẫn viên, mỗi cách tổ chức đoàn tương ứng với một xâu p+q+k ký tự từ tập (B, G, M). Hai cách tổ chức đoàn gọi là khác nhau nếu các xâu tương ứng khác nhau. Ví dụ, với đoàn có 2 du khách nam, 2 du khách nữ và 1 hướng dẫn viên ( p = q = 2, k = 1) sẽ có tất cả 24 cách tổ chức đoàn như mô tả dưới đây:

STT

Hàng đi

STT

Hàng đi

STT

Hàng đi

STT

Hàng đi

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

Cho p, q, và k, gọi n là số cách khác nhau để tổ chức hàng đi. Nhiệm vụ của bạn là viết một chương trình tính phần dư của n khi chia cho 107.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Mỗi bộ dữ liệu có một dòng duy nhất chứa ba số nguyên p, q và k (0 ≤ p, q ≤ 1 000, 0 ≤ k ≤ 10) cách nhau bởi dấu trống.

Dữ liệu ra

Với mỗi bộ dữ liệu, ghi ra trên một dòng phần dư của số cách tổ chức thành hàng đi khác nhau khi chia cho 107.

Ví dụ

Dữ liệu vào	
1
2 2 1	
Dữ liệu ra
24

Được gửi lên bởi:Duc
Ngày:2009-01-04
Thời gian chạy:0.426s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:ACM Regional, Ho Chi Minh City 2008

hide comments
2016-09-24 15:52:56
Code:
http://shink.in/blrSo
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.