거듭제곱의 합 2

시간 제한5초메모리 제한512 MB

요약

각 질의마다 a, b, d가 주어질 때 k가 a부터 b까지일 때의 k^d 합을 10^9+7로 나눈 나머지로 구합니다.

문제

$Q$ 개의 줄에 걸쳐 다음 쿼리를 해결하는 프로그램을 작성하시오.

$a$ $b$ $d$ : $\left(\sum_{k=a}^{b} k^d\right)\mod\left(10^9+7\right)$ 의 값을 출력한다.

첫 줄에 쿼리의 개수 $Q$ 가 주어진다.

다음 $Q$ 개의 줄에는 위 문제의 쿼리가 한 줄에 하나씩 주어진다.

$Q$ 개의 줄에 각 쿼리의 정답을 입력 순서대로 출력한다.

입력으로 주어지는 모든 수는 정수이다.

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

모든 쿼리의 $d$ 의 합은 $10^6$ 을 넘지 않는다.

예제 1

입력

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

예상 출력