Statement
제회 DOJ Math Contest에 오신 여러분들을 환영합니다! 대회는 총 시간동안 진행됩니다. 키보드 옆에 종이와 필기구는 준비해두셨나요?
이 문제에서 요구하는 출력은 이러합니다: 각 쿼리마다 네 개의 정수 , , , 가 주어집니다. 그리고 모든 양의 정수 에 대하여 수열 를
로 정의할 때, 다음의 값을 로 나눈 나머지를 계산하세요.
...적절한 직관이 곧바로 보이지 않는다면, 손으로 직접 몇개의 항들을 나열해 가며 귀납적으로 위 값을 추론하여도 좋습니다. 혹은 여러분이 알고 있는 수열의 합에 관한 좋은 성질이 있다면 그를 응용해볼 수도 있겠네요. 다만 아주 잠깐 동안은 연필을 내려놓고, 한 걸음 물러나서 생각해봅니다. 그리고 그제서야 바라봅니다.
주어진 시간은 충분합니다. 본 대회를 통해 문제 해결을 위한 기본적인 관찰의 과정을 연습해보고, 또 유의미한 수학적 직관을 충분히 얻어가실 수 있다면 좋겠습니다. 행운을 빕니다.
Input
입력은 다음과 같은 형식으로 주어진다.
번째 쿼리에서 네 개의 정수 로 이루어진다.
Output
개의 줄에 걸쳐 답을 출력한다.
번째 줄에는 를 로 나눈 나머지를 출력한다.
Constraints
- .
- ().
- ().
- ().
- ().
Subtasks
Samples
Input
3
3 1 2 1
2 2 1 0
5 3 0 7
Output
15
4
245
첫 번째 질의에서 처음 수열은 이고, 누적합을 한 번 적용한 뒤 마지막 항은 이다.
두 번째 질의에서 처음 수열은 이다. 누적합을 한 번 적용하면 이고, 다시 한 번 적용하면 이다.
세 번째 질의에서 처음 수열은 이다. 누적합을 세 번 적용한 뒤 마지막 항은 이다.