TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

82.4% (14/17)

Tags

Description

千辛萬苦拿到鑰匙的妁艷,以極快的速度衝刺到那扇門,打開門之後便是一陣凝重的氣息。當妁艷正想繼續衝刺時,他在樓梯的底部發現事情不大對,有一群女同學正在接近妁艷!

「葛~格~。」她們無意識的叫著妁艷,彷彿受到甚麼東西控制了。雖然妁艷不想傷害她們,不過時間緊迫,他只好拿出武器應戰。

在妁艷伶俐的攻勢之下,敵人一個一個倒下,但是妁艷發現敵人數量好像沒有減少,他才知道敵人倒下之後過幾分鐘就會復活,「這個學校到底發生了什麼事?」妁艷心中產生疑惑。

在妁艷觀察之下,妁艷查覺出了怪異之處,就是她們身上都有一串印記,分別是有N個數字,並且有著這樣的規律

K_(n+2)=K_(n+1)+K_n

「5!」妁艷大叫,其中一個敵人身體顫抖,表情顯現出痛苦與快樂,而且她的印記消失了。

原來這種敵人只要等她倒地時喊出印記的最後一項數字(mod 1,000,000,007)就能造成絕頂的傷害,並且使其真正解放。

但由於妁艷戰鬥時激烈的摩擦,每個敵人身上第2項之後的印記都被妁艷磨掉了,幸運的是妁艷都記得每個敵人的印記有幾項。

妁艷順利的解放所有敵人嗎?還是他會因此耗盡精力呢?

Input Format

第一行有數字t,代表有t個敵人
接下來有t行,每行有三個數字K_1,K_2,N,代表印記第一項和第二項以及解放所需的是第幾項
1<=t<=100000
0<=K_1,K_2<=9223372036854775807
2<=N<=9223372036854775807

Output Format

對每個敵人輸出K_N(mod 1,000,000,007)

Sample Input

3
1 1 5
1 3 5
1 5 5

Sample Output

5
11
17

Hints

第一個敵人印記:1 1 2 3 5
第二個敵人印記:1 3 4 7 11
第三個敵人印記:1 5 6 11 17

Problem Source

原TIOJ1757 / problem setter:fenzhang

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

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