34851번 - 사칙연산 게임

문제

쿠옹이는 $N+1$개의 양의 정수로 구성된 수열을 가지고 있다. 쿠옹이는 모든 인접한 두 수 사이에 연산자를 하나씩 총 $N$개를 삽입해 연산 결과를 최대로 하고 싶다.

사용할 수 있는 연산은 덧셈, 뺄셈, 곱셈, 나눗셈의 4ドル$종류이며 모든 연산은 일반적인 연산자 우선순위가 아니라 왼쪽에서 오른쪽 순서로 시행된다. 단, 나누어떨어지지 않을 때 나누는 것은 금지된다.

쿠옹이를 도와 연산 결과의 최댓값을 구해 보자.

입력

첫째 줄에 $N$이 주어진다. (1ドル \le N \le 5 \times 10^{5}$)

둘째 줄에 $N+1$개의 정수 $a_{1},ドル $a_{2},ドル $\cdots,ドル $a_{N+1}$이 공백으로 구분되어 주어진다. (1ドル \le a_{i} \le 10^{9}$)

출력

모든 간격에 원하는 연산자를 삽입하였을 때 연산 결과를 출력한다. 단, 결과값이 너무 커질 수 있으므로 10ドル^{9}+7$로 나눈 나머지를 대신 출력한다.

제한

노트