Save King Kala

4.6

19 votes
Medium
Problem

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

Time Limit: 1
Memory Limit: 256
Source Limit:
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

Editor Image

?