순찰 드론의 비행 모드

RiseOJ 연구소의 순찰 드론은 \(N\)개의 구간을 순서대로 비행해야 한다.

각 구간에서는 다음 두 비행 모드 중 하나를 선택한다.

• 일반 모드: \(i\)번째 구간에서 에너지 \(A_i\)를 사용한다.
• 터보 모드: \(i\)번째 구간에서 에너지 \(B_i\)를 사용한다.

터보 모드는 모터의 열을 크게 올리기 때문에 서로 인접한 두 구간에서 연속으로 사용할 수 없다. 일반 모드는 연속으로 사용해도 된다.

모든 구간을 비행하는 데 필요한 에너지의 최솟값과, 그 최솟값을 만드는 서로 다른 모드 선택 방법의 수를 구하여라. 두 방법은 한 구간에서라도 선택한 모드가 다르면 서로 다른 방법이다.

• \(1 \le N \le 200\,000\)
• \(0 \le A_i, B_i \le 10^9\)
• 모든 입력은 정수이다.
• 최소 에너지는 64비트 정수 범위에 들어간다.

첫째 줄에 구간의 수 \(N\)이 주어진다.

다음 \(N\)개의 줄 중 \(i\)번째 줄에 두 정수 \(A_i\), \(B_i\)가 주어진다.

첫째 줄에 최소 에너지와 그 최소 에너지를 만드는 방법의 수를 공백으로 구분하여 출력한다.

방법의 수는 \(1\,000\,000\,007\)로 나눈 나머지를 출력한다.

rip 작성

출처 RiseOJ Original