#216 summation

Statement

제 $1$ 회 DOJ Math Contest에 오신 여러분들을 환영합니다! 대회는 총 $42$ 시간동안 진행됩니다. 키보드 옆에 종이와 필기구는 준비해두셨나요?

이 문제에서 요구하는 출력은 이러합니다: 각 쿼리마다 네 개의 정수 $N$ , $M$ , $a$ , $b$ 가 주어집니다. 그리고 모든 양의 정수 $i$ 에 대하여 수열 $\{A_i\}$ 를

A_i=ai+b

로 정의할 때, 다음의 값을 $1\ 000\ 000\ 007$ 로 나눈 나머지를 계산하세요.

S(N,M,a,b)=\overbrace{\sum_{i_M=1}^N \ \sum_{i_{M-1}=1}^{i_{M}} \cdots \ \sum_{i_{2}=1}^{i_{3}} \ \sum_{i_{1}=1}^{i_{2}}}^{M\text{개}} A_{i_1} .

...적절한 직관이 곧바로 보이지 않는다면, 손으로 직접 몇개의 항들을 나열해 가며 귀납적으로 위 값을 추론하여도 좋습니다. 혹은 여러분이 알고 있는 수열의 합에 관한 좋은 성질이 있다면 그를 응용해볼 수도 있겠네요. 다만 아주 잠깐 동안은 연필을 내려놓고, 한 걸음 물러나서 생각해봅니다. 그리고 그제서야 바라봅니다.

주어진 시간은 충분합니다. 본 대회를 통해 문제 해결을 위한 기본적인 관찰의 과정을 연습해보고, 또 유의미한 수학적 직관을 충분히 얻어가실 수 있다면 좋겠습니다. 행운을 빕니다.

Input

입력은 다음과 같은 형식으로 주어진다.

$Q$ $N_1\ M_1\ a_1\ b_1$ $N_2\ M_2\ a_2\ b_2$ $\vdots$ $N_Q\ M_Q\ a_Q\ b_Q$

$q$ 번째 쿼리에서 네 개의 정수 $N_q,M_q,a_q,b_q$ 로 이루어진다.

Output

$Q$ 개의 줄에 걸쳐 답을 출력한다.

$q$ 번째 줄에는 $S(N_q,M_q,a_q,b_q)$ 를 $1\ 000\ 000\ 007$ 로 나눈 나머지를 출력한다.

Constraints

$1 \leq Q \leq 200\ 000$ .
$1 \leq N_q \leq 200\ 000$ ( $1 \leq q \leq Q$ ).
$1 \leq M_q \leq 200\ 000$ ( $1 \leq q \leq Q$ ).
$0 \leq a_q \leq 1\ 000\ 000\ 000$ ( $1 \leq q \leq Q$ ).
$0 \leq b_q \leq 1\ 000\ 000\ 000$ ( $1 \leq q \leq Q$ ).

Subtasks

#	Score	Constraints
1	13	$Q \leq 20$ . $N_q \leq 20$ ( $1 \leq q \leq Q$ ). $M_q \leq 20$ ( $1 \leq q \leq Q$ ).
2	20	$Q \leq 2\ 000$ . $N_q \leq 2\ 000$ ( $1 \leq q \leq Q$ ). $M_q \leq 2\ 000$ ( $1 \leq q \leq Q$ ).
3	17	$a_q=0$ ( $1 \leq q \leq Q$ ).
4	17	$M_q=1$ ( $1 \leq q \leq Q$ ).
5	33	추가적인 제약조건이 없다.

Samples

Input

Output

15
4
245

첫 번째 질의에서 처음 수열은 $3,5,7$ 이고, 누적합을 한 번 적용한 뒤 마지막 항은 $15$ 이다.

두 번째 질의에서 처음 수열은 $1,2$ 이다. 누적합을 한 번 적용하면 $1,3$ 이고, 다시 한 번 적용하면 $1,4$ 이다.

세 번째 질의에서 처음 수열은 $7,7,7,7,7$ 이다. 누적합을 세 번 적용한 뒤 마지막 항은 $245$ 이다.

Editorial

View editorial

말랑말랑 계산 직관 트레이닝

Statement

Input

Output

Constraints

Subtasks

Samples

Editorial