Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem B: 二队-上海-答题游戏

Problem B: 二队-上海-答题游戏

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 165  Solved: 20
[Submit][Status][Web Board]

Description

小A参加了一个答题游戏,每答对一题加一分,每连续答对k题总积分翻倍,并清零计数器。已知一共有n题,小A答对了m题,问小A最少可能拿到多少分?

Input

第一行一个正整数T(T<=100),表示共有T组数据。
对于每组数据,一行三个正整数n,m,k(2<=n,k<=10^9;0<=m<=n)。

Output

对每组数据输出一行,即小A最少可以拿到的分数(答案可能过大,请对1e9+9取模)。

Sample Input

1
5 4 2

Sample Output

6

HINT

[Submit][Status][Web Board]