문제

당신은 주어진 스케이트 코스에서 번의 스케이트 연습을 하려고 한다. 전체 코스는 총 개의 지점으로 이루어져 있으며, 각 지점은 고유한 번호가 부여되어 있다. 지점의 번호는 번부터 시작하여 번까지, 즉 순서로 붙어 있다.

번째 연습에는 번 지점에서 연습을 시작하여 번 지점과 번 지점을 거쳐 번 지점에서 연습을 끝낸다. 따라서 번째 연습 경로는 와 같다. 매 연습 경로는 다를 수도 있다.

이 연습은 번 지점에서 의 속력으로 출발하여, 번 지점에 의 속력으로 도착한다. 번 지점에는 속력 제한 가 있어, 다음으로 방문할 지점의 속력 제한을 초과하지 않도록 이동하는 사이에 속력을 조절해야 한다. 속력을 높일 때는 원하는 만큼 높일 수 있지만, 속력을 낮추는 경우에는 마지막으로 방문했던 지점에서의 속력에서 만큼만 낮출 수 있다.

단, 번 지점과 번 지점을 제외한 위치에서 속력은 이 될 수 없다. 속력을 변경하지 않고 그대로 유지하는 것도 가능하다. 지점별 속도 제한 는 모든 연습에서 동일하다.

연습의 성과는 각 지점에서의 속력의 합과 같으므로 이를 최대화하려고 한다. 스케이트 코스의 속력 제한이 주어졌을 때, 각 연습마다 얻을 수 있는 최대 연습의 성과를 구해보자. 단 성과가 너무 커질 수 있으므로, 최대 성과를 으로 나눈 나머지를 출력하여라.

입력

이 문제에서 값은 직접 주어지지 않고 유사 난수 생성기로 생성한 것을 사용할 것이다. 자세한 사용법은 아래에 기술되어 있다.

첫 번째 줄에 양의 정수 이 주어진다. ()

두 번째 줄에 의 값을 생성하기 위한 세 개의 정수 가 공백을 두고 주어진다. (|단, )

세 번째 줄에 양의 정수 가 주어진다. ()

네 번째 줄에 값을 생성하기 위한 다섯 개의 정수 가 공백을 두고 주어진다.
(|단, )

출력

개의 줄에 걸쳐 번째 줄에는 번째 연습의 최대 성과를 으로 나눈 나머지를 출력하여라.

유사 난수 생성기

다음은 각 언어별로 문제의 유사 난수 생성기를 구현한 코드이다. 언어에 맞는 코드를 그대로 사용하면 된다. 유사 난수 생성 방법과 문제의 풀이와는 관련이 없음이 보장된다.

• C/C++ : https://onlinegdb.com/dpcDkEEWx
• Python : https://onlinegdb.com/LL8tg_USZ

함수 목록

• get_random(x, y) : x 이상 y 이하의 범위에서 임의의 정수를 반환한다.
• ready(seeds) : 첫 seed 값을 설정한다.

값을 구하는 방법

• : 먼저 ready()를 호출한 뒤, get_random()를 번 호출하여 반환되는 값을 순서대로 으로 정한다. 이렇게 구한 값들은 항상 를 만족한다.
• : 먼저 ready()를 호출한 뒤, get_random()를 호출하여 값을 구하고, 이어서 get_random(max(), )를 호출하여 값을 구한다. 이 과정을 번 반복하여, 순서대로 를 정한다. 이렇게 구한 값들은 항상 을 만족한다.

즉 함수 호출 흐름은 다음과 같다 :

ready() -> get_random() -> -> get_random() -> ready() -> get_random() -> get_random(max(),) -> -> get_random() -> get_random(max(),)