31987번 - ESC와 쿼리

문제

미분가능한 함수 $\text{ESC}(x) = e^x \sin x \cos x$를 $n$번 미분한 결과를 $\text{ESC}^{(n)}(x)$라 하자. $\text{ESC}^{(n)}(x)$는 다음과 같이 표현할 수 있다.

• $\text{ESC}^{(n)}(x)=a_n e^x \sin ^2 x + b_n e^x \cos ^2 x + c_n e^x \sin x \cos x$ (단, $a_n,ドル $b_n,ドル $c_n$은 정수)

다음 쿼리를 수행하는 프로그램을 작성하시오.

• i j k: $\sum_{x=i}^{j} a_{kx}+b_{kx}+c_{kx}$ 값을 출력한다. (단, $i,ドル $j,ドル $k$는 양의 정수)

쿼리 결과의 절댓값이 매우 클 수 있으므로 쿼리의 결과를 세 정수 $p,ドル $q,ドル $r$에 관한 식 $p \times q + r$로 표현할 때, $r$을 대신 출력한다. $(0 \le r \lt p=10^9+7)$

입력

첫 번째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \le Q \le 10^5)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다. $(1 \le i \le j \le jk \lt 2^{31})$

출력

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

제한

힌트