cho.sh

J

아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제

J 프로그래밍 언어는 1990년대 초에 Kenneth E. Iverson과 Roger Hui가 만들었다. Iverson이 설계한 APL과 John Backus가 만든 함수 수준 언어 FP, FL을 합친 언어다.

위키백과. J (프로그래밍 언어)

APL 계열 언어는 벡터와 배열을 통째로 다루는 연산으로 유명하고 J도 마찬가지다. 이 계열에서는 모든 단항, 이항 수치 연산이 차원이 서로 다른 벡터와 배열에도 기본으로 적용된다. 예를 들어 덧셈 +는 스칼라와 스칼라를 더하고, 스칼라와 벡터도 더하고, 벡터와 벡터도 더한다. 스칼라와 벡터를 더하면 스칼라를 벡터의 각 성분에 더하고, 벡터와 벡터를 더하면 같은 자리의 성분끼리 더한다.

J의 표현력은 놀랍고 문법은 그만큼 난해하지만, 이 문제에서는 언어의 아주 작은 일부만 쓴다. 벡터 변수 X 하나와 X의 길이인 스칼라 변수 N 하나, 그리고 다음 연산으로 이루어진 식 하나를 생각한다.

  • 벡터와 벡터, 벡터와 스칼라, 스칼라와 스칼라를 더하고(+), 빼고(-), 곱할(*) 수 있다.
  • 스칼라와 벡터에 단항 마이너스(-)와 단항 제곱(*:)을 쓸 수 있다. 벡터에는 성분마다 적용한다.
  • 벡터를 덧셈으로 접을 수 있다(+/). 벡터의 모든 성분을 더한 값을 주는 단항 연산이다.

J는 연산자의 자연스러운 우선순위를 무시하고 오른쪽에서 왼쪽으로 계산한다. 계산 순서는 괄호로 바꾼다. 정확한 문법은 아래 BNF와 같다.

⟨식⟩ ::= ⟨항⟩ | ⟨항⟩ ('+' | '-' | '*') ⟨식⟩ | ('-' | '*:' | '+/') ⟨식⟩
⟨항⟩ ::= '(' ⟨식⟩ ')' | 'X' | 'N' | ⟨수⟩
⟨수⟩ ::= ('0' | '1' | ... | '9')+

식의 문법에는 제한이 하나 더 붙는다. 이를 정확히 쓰기 위해 식의 복잡도를 다음과 같이 정의한다.

  • 스칼라(수, N, 접기 결과)의 복잡도는 0이다.
  • X의 복잡도는 1이다.
  • 덧셈과 뺄셈의 복잡도는 두 피연산자의 복잡도 중 큰 값이다.
  • 곱셈의 복잡도는 두 피연산자의 복잡도를 더한 값이다.
  • 단항 제곱의 복잡도는 피연산자의 복잡도의 두 배다.

예를 들어 식 (3-+/*:*:X)-X**:X의 복잡도는 3이고, 그 부분식 *:*:X의 복잡도는 4이다.

스칼라 값을 갖는 식과 벡터 X의 값이 주어진다. 식의 값을 10910^9으로 나눈 나머지를 구하라. 주어진 식의 모든 부분식은 복잡도가 10 이하다.

입력

첫째 줄에 벡터 X의 길이 NN이 주어진다. (1≤N≤1051 \le N \le 10^5)

둘째 줄에 벡터 X의 성분 NN개가 주어진다. (0≤Xi<1090 \le X_i < 10^9)

셋째 줄에 계산할 식이 주어진다. 식은 비어 있지 않고 길이가 10510^5 이하이며, 식에 나오는 수는 모두 10910^9 미만이다. 접기는 스칼라에 적용되지 않는다.

출력

식의 값을 10910^9으로 나눈 나머지를 정수 하나로 출력한다. 나머지는 항상 00 이상 10910^9 미만이므로, 식의 실제 값이 음수이면 음이 아닌 나머지로 바꿔서 출력한다.

힌트

+/*:X는 유클리드 거리에서 잰 벡터 X의 길이의 제곱이다.

N++/X-X+1의 값은 X와 무관하게 항상 0이다.

X가 (11, 56, 37)일 때 +/(3-+/*:*:X)-X**:X의 실제 값은 -35397485이고, 출력하는 답은 이 값을 10910^9으로 나눈 나머지다.