Sum of Powers 2

Time limit5sMemory limit512 MB

Summary

For each query with a, b, and d, compute the sum of k^d for k from a to b, modulo 10^9+7.

Problem

Write a program that answers the following queries over $Q$ lines.

$a$ $b$ $d$ : Print the value of $\left(\sum_{k=a}^{b} k^d\right)\mod\left(10^9+7\right)$ .

The first line contains the number of queries $Q$ .

Each of the next $Q$ lines contains one query from the problem, one per line.

Print the answer to each query on its own line, in the same order as the input.

All numbers in the input are integers.

$1\leq Q\leq 10^6$ , $1\leq a\leq b\leq 10^9$ , $0\leq d\leq 10^5$

The sum of $d$ over all queries does not exceed $10^6$ .

Example 1

Input

5
1 100 1
50 100 2
1000 9999 3
1000000000 1000000000 100000
100000000 999999999 0

Expected output