연속 구간의 자전거 거점

문제

공유 자전거 운영팀은 일직선 산책로에 있는 N개의 거점 중 일부를 야간 운영 거점으로 지정하려 한다. 거점에는 산책로를 따라 1번부터 N번까지 번호가 붙어 있다. i번 거점을 지정하면 조명과 잠금 장치를 유지하는 데 정수 C_i만큼의 비용이 든다. 지정하지 않은 거점에서는 야간에 자전거를 빌리거나 반납할 수 없다. 운영팀은 이용자가 운영 거점을 찾기 위해 너무 멀리 이동하지 않도록 다음 규칙을 정했다. 번호가 연속한 두 거점 i와 i+1에 대해서는 적어도 한 곳이 야간 운영 거점이어야 한다. 이 규칙은 1 ≤ i < N인 모든 i에 적용된다. 즉, 지정하지 않은 거점이 두 곳 이상 연속해서 나타나면 안 된다. 서로 이웃한 두 거점을 모두 지정하는 것은 허용하며, 지정한 거점의 개수에는 별도의 제한이 없다. 전체 비용은 지정한 거점들의 비용을 더한 값이다. 비용은 거점마다 한 번만 발생하고, 서로 떨어진 거점을 함께 지정한다고 해서 할인이나 추가 비용이 생기지 않는다. 운영팀은 규칙을 지키면서 전체 비용을 최소화하려 한다. 또한 같은 최소 비용을 만드는 운영 계획이 여러 개일 수 있으므로, 그러한 계획의 수도 함께 알고 싶어 한다. 운영 계획은 지정한 거점 번호의 집합으로 구분한다. 지정한 순서만 다른 경우는 같은 계획이다. 비용이 같은 거점이라도 번호가 다르면 서로 다른 거점이며, 비용이 0인 거점을 추가로 지정한 계획도 지정 집합이 달라지면 별개의 계획이다. 산책로 양 끝 바깥에는 거점이 없으므로, 첫 번째나 마지막 거점을 반드시 지정해야 한다는 추가 조건은 없다. N이 1이면 연속한 두 거점 자체가 없으므로 아무 거점도 지정하지 않는 계획도 규칙을 만족한다. 모든 거점을 지정하는 계획은 항상 가능하므로 해가 없는 입력은 주어지지 않는다. 최소 비용은 정확한 정수로 출력하고, 최소 비용을 만드는 계획의 수는 1,000,000,007로 나눈 나머지를 출력한다.

입력

첫째 줄에 정수 N이 주어진다. 1 ≤ N ≤ 40,000이다.
둘째 줄에 정수 C_1, ..., C_N이 공백으로 주어진다. 0 ≤ C_i ≤ 1,000,000이다.

출력

첫째 줄에 최소 전체 비용과 그 비용을 만드는 운영 계획의 수를 공백으로 구분하여 출력한다. 계획의 수는 1,000,000,007로 나눈 나머지를 출력한다.

4
3 1 1 3

2 1

3
0 0 0

0 5

1
7

0 1

출처: Devin.KR 자체 제작