SP3646 ATOURISM - Adventure Tourism

近来，冒险旅游越来越受到欢迎。然而，组织这样的旅行却不是一件简单的事，因为它需要非常细致的准备，并注意到具体的细节。 这次旅行有 $p$ 名男参与者和 $q$ 名女参与者。除此之外，组织者还特意安排了 $k$ 名导游同行。在旅行的开头阶段，道路非常狭窄，而且经过悬崖；所以队伍需要依次排成一条直线。为了确保相互之间能够提供帮助，要求每一位女性参与者旁边（即前后）都必须是一名男性参与者或者一名导游。此外，至少有一个参与者必须紧邻一名导游。基于这些限制条件，我们可以有多种方式来排列队伍。我们用 $B$ 来代表男参与者，$G$ 来表示女参与者，$M$ 表示导游。排列队伍的方式可以用一个长度为 $(p+q+k)$ 的字符串来表示，该字符串由字符集 $(B, G, M)$ 中的字符组成。如果两个排列的字符串不相同，则它们是两种不同的排列方式。例如，有 2 名男性、2 名女性和 1 名导游（$p = q = 2, k = 1$）时，队伍可以有 24 种不同的排列方式，如下表所示： | **索引** | **队伍排列** | **索引** | **队伍排列** | **索引** | **队伍排列** | **索引** | **队伍排列** | | -------- | ------------ | -------- | ------------ | -------- | ------------ | -------- | ------------ | | **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 | 给定 $p$、$q$ 和 $k$，计算有多少种不同的队伍排列方式，最后输出这个数量除以 $10^7$ 的余数。

输入文件包含多个数据集。第一行是数据集数量的正整数，不会超过 20。接下来的每一行描述一个数据集。 对于每个数据集，输入一行包括三个以空格分隔的整数 $p$、$q$ 和 $k$（$0 \le p, q \le 1000, 0 \le k \le 10$）。

对于每个数据集，输出一行，表示不同排列方式的数量除以 $10^7$ 的余数。 **本翻译由 AI 自动生成**