게임 서버의 묶음 처리 계획

문제

한 게임 서버는 다음 운영 구간에 실행할 작업을 시간순으로 N개 준비했다. 작업에는 1번부터 N번까지 번호가 붙어 있으며, 서버는 이 순서를 유지하면서 모든 작업을 정확히 한 번 처리해야 한다. 작업을 실행하는 방식에 따라 처리 효율이 달라지므로, 관리 프로그램은 전체 효율 점수가 가장 높은 처리 계획과 그러한 계획의 수를 계산하려 한다. 서버가 한 번에 실행할 수 있는 묶음은 두 종류다. 하나는 작업 한 개만 처리하는 단독 묶음이고, 다른 하나는 번호가 연속한 작업 두 개를 함께 처리하는 결합 묶음이다. 단독 묶음으로 i번 작업을 처리하면 A_i점을 얻는다. 결합 묶음으로 i번과 i+1번 작업을 함께 처리하면 B_i점을 얻는다. 결합 묶음의 점수는 B_i 자체이며, A_i와 A_{i+1}을 추가로 더하지 않는다. 세 개 이상의 작업을 한 묶음으로 처리할 수는 없다. 처리 계획은 1번부터 N번까지의 작업을 길이가 1 또는 2인 연속한 묶음들로 나눈 결과다. 어떤 작업도 건너뛰거나 두 묶음에 중복하여 넣을 수 없다. 묶음들은 작업 번호가 작은 것부터 실행하며, 실행 순서를 따로 바꾸는 선택은 없다. 점수가 음수인 작업도 반드시 어느 묶음에 포함하여 처리해야 한다. 계획의 전체 점수는 각 묶음에서 얻는 점수의 합이다. 두 계획은 묶음의 경계가 하나라도 다르면 서로 다른 계획으로 센다. 같은 경계를 가진 계획은 점수 계산 과정과 관계없이 하나로 센다. 전체 점수가 같은 최적 계획이 여러 개라면 어느 하나를 고르는 대신 그 개수를 구한다. 모든 작업을 처리할 수 있는 계획은 항상 존재한다. 가능한 전체 점수의 최댓값과, 그 최댓값을 얻는 계획의 수를 1,000,000,007로 나눈 나머지를 출력한다.

입력

첫째 줄에 정수 N이 주어진다. 1 ≤ N ≤ 40,000이다.
다음 N개 줄 중 i번째 줄에 정수 A_i와 B_i가 공백으로 구분되어 주어진다. -9 ≤ A_i ≤ 9이다. i < N이면 -9 ≤ B_i ≤ 9이다. B_N은 항상 0이며 어떤 묶음의 점수로도 사용하지 않는다.

출력

최대 전체 점수와 그 점수를 얻는 서로 다른 처리 계획 수를 1,000,000,007로 나눈 나머지를 공백으로 구분하여 한 줄에 출력한다. 최대 전체 점수에는 나머지 연산을 적용하지 않는다.

3
2 5
1 4
2 0

7 1

4
0 0
0 0
0 0
0 0

0 5

2
-3 -8
-2 0

-5 1

출처: Devin.KR 자체 제작