save-king-kala
Source: hackerearth
Difficulty: MEDIUM

King Kala underestimated the power of King Kushu and launched an unprepared attack on King Kushu’s Kingdom. But King Kushu already knew about King Kala’s plans through his favourite  undercover agent  Brojiya. He crushed King Kala’s army in a very short span of time.

Unlike King Kala, King Kushu being good hearted and a lover of mathematics gave a problem to him. He promised King Kala that he would give back his kingdom under the condition that he solves this problem.

Given non negative integer P, a positive odd integer K and two positive integers A and B, determine the sum of  numbers between A and B to the power P that contain exactly K divisors. As the sum can be very large King Kushu wants the sum modulo 10000000000037.

King Kala hates mathematics and gives this problem to you. Help King Kala get back his kingdom.

*Input : *

First line contains 2 integers T, the number of test cases and P. The next T lines contains 3 integers K, A, B.

*Output : *

Print the required sum modulo 10000000000037 for each test case in a new line.

*Constraints : *

1 ≤ T ≤ 100000
0 ≤ P ≤ 100
1 ≤ K ≤ 10000 (K is odd)
1 ≤ A ≤ B ≤ 10^10

SAMPLE INPUT
1 1
9 1 100

SAMPLE OUTPUT
136

Explanation

There are only 2 numbers between 1 and 100 which have number of divisors = 9.

Divisors of 36 are 1, 2, 3, 4, 6, 9, 12, 18, 36
Divisors of 100 are 1, 2, 4, 5, 10, 20, 25, 50, 100

Thus required answer is 36^1 + 100^1 = 36 + 100 = 136