거듭제곱의 합 2

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

• $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$을 넘지 않는다.