Limits 2s, 1.0 GB

Ray and Evangeline are playing a game named "The Lucky Dice". In this game, each player tosses up an nn sided special fair dice' alternatively. This continues for kk turns. In each turn two players both roll the dice once. Then the players add all the numbers they got and the person with the higher sum wins.

A fair dice is a dice that has n sides and each side has the same probability of coming up while tossed up. An nn sided special fair dice' is a fair dice which has LL, L+1L+1, L+2L+2, L+3L+3, ..., L+n1L+n-1 written on its nn sides.

They invited you to watch their game. But as it can be boring just to sit there, they want you to take part too. So, As they play you'll try to guess the sum of all dice tosses (you'll guess before the first dice being tossed). You are desperate to win this challenge.

Can you find out what guess will give you the most chance of winning?

Input

Input starts with an integer TT (0<T<110 < T < 11), denoting number of test cases.

The next TT lines contains three integers nn, kk, LL (0<n,k,l<10120 < n,k,l < 10^{12}) as described above.

Output

For each test case, print a number in one line containing your answer to that test case.

As the answers can be big, print it modulo 101810^{18}. If there are multiple answers, print any of them.

Sample

InputOutput
1
6 1 1
7

Submit

Login to submit.

Statistics

66% Solution Ratio
arknaveEarliest, Dec '19
RamprosadGFastest, 0.0s
RamprosadGLightest, 0 B
bokaifShortest, 79B
Toph uses cookies. By continuing you agree to our Cookie Policy.