TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

24.1% (7/29)

Tags

Description

妁艷打開了學校大門進了學校,發現學校內異常的陰森黑暗又安靜。才沒走幾步,突然身後的大門關上了,警衛、幾位老師、還有一群的警察出現在大門外,更讓妁艷感到事情的嚴重性。

妁艷走回門邊,有老師跟妁艷說明了事情:「今天下午,就在某節下課,所有的學生就像中了邪一樣,不知道受了甚麼操控,行為和眼神都顯得極度怪異,師長們都驚惶的逃出了學校,並關上了學校。我們比較勇敢的幾個老師後來去了警察局,警察也直到剛剛才相信了我們所說的,並決定要封鎖住整間學校……你怎麼會跑進去…?」

妁艷急忙的想打開大門離開學校,卻發現大門的鎖不知何時已經壞了。

妁艷變的相當的慌張,這時,他的爸媽出現了,爸爸對他說:「兒子,仔細聽好......其實我們家世世代代每人都有一個特殊的強力武器,那武器一直都在你身上,只不過你沒發覺而已......,每當這世界遭受到危機,就是要拿起武器打敗敵人的時候了!這次,或許是個有邪惡法力的不明生命體吧(?)操縱了這間學校的每位學生,拿起你的武器,跟學生們戰鬥吧,只要能讓所有被入侵的學生解放,就能獲得勝利!」

妁艷在身上摸索了一番,還真有一把看似強力的武器。他和眾人揮了揮手,轉過頭去,並踏上了旅程。

妁艷當下第一件事就是想趕快救出妹妹,於是就先跑到了妹妹社團的辦公室。

「哥哥你終於來了!!」妁艷才接近社辦,就聽到了妹妹的呼喊。

他急忙的衝進社辦,卻發現這是個陷阱!

一個社團的社員已經中了魔法,眼神怪異的看著妁艷,將門給鎖上,並且準備攻向妁艷!

妁艷很清楚,到了戰鬥的時候了。

「解放他吧」他想著。


妁艷立刻拿起武器,到了一個最好施放武器的絕佳位置X,卻發現自己因為等級太低,武器無法立刻使用,必須要等m秒過後才能使用。

也就是說妁艷第0秒在X處,在第m秒也得在X處。

因為敵人會追著妁艷攻擊,所以當他在某一秒踏上某一處後,下一秒就不能待在那一處了。

而且敵人還會開大絕分身,分成共K個敵人輪流站上妁艷踩上的地方。

所以就變成妁艷踩過某處(包括第0秒在X處)後,那個地方接下來會有K秒都不能再踩上去了。

還有,妁艷把社辦分成了n處(包括X處)。

原本敵人都不在此n處上。

(這裡所述的n個地點皆不用管其相對位置關係之類的)

幫妁艷算出有幾種辦法可以免於被攻擊,並在第m秒時踏回X處。

Input Format

第一行有一個數字T(1≤ T≤100)代表有T筆資料妁艷想請你算
之後會有T行,每行有三個數n、m、K(1≤ n,m,K≤1000),代表題目中的n、m、K。

Output Format

對於每筆資料各輸出一行答案,總共要輸出T行。

因為答案可能太大所以一律都 mod 1000000007

Sample Input

4
5 3 1
5 3 3
6 4 1
6 4 2

Sample Output

12
0
105
60

Hints

Problem Source

原TIOJ1754 / problem setter: lnsuyn

Subtasks

No. Testdata Range Score
1 0 25
2 1 25
3 2 25
4 3 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4