Mr. Billionare is a very rich person. He has won many prizes for his brilliant works in the field of mathematics and that's how he became so rich. Today, he has decided to give some of his money to a charity. You are required to raise the maximum possible amount for the charity.

He will give you a range of numbers from 'a' to 'b' (both inclusive ) and a number x. You have to find the product of the function F for all the numbers in the range.

The product will denote the amount Mr. Billionare will dontate to the charity.

Function F is defined as follows-

F(i) = maximum of ( i, rich(i), rich(rich(i)), rich(rich(rich(i))), ......   ) for a given value of x

rich(N) is defined as - raise each of digits of N to the xth power and sum those values.

Input:

First line of input contains T denoting the number of testcases.

T lines follow each containing 3 integers denoting the values a,b,x. The range is from a to b and the x is the power to which each digit has to be raised.

Output

Print the answer to each testcase in a new line.

Print the answer Modulo 10^9+7.

Constraints

1<=T<=100

1<=a<=1000000

1<=b<=1000000

1<=k<=6

Problem Setter

Shikhar Kunal