23313번 - K-계산기

두유노 김치?

두유노 이국렬?

두유노 계산기? 펄~럭

국렬이는 세 번이나 계산기 문제를 내놓고 또 계산기 문제를 냈다. 언제까지 나오는지 지켜보자. 당신은 또 계산기 문제를 만나서 귀찮지만 상금을 얻기 위해서 주어진 수식을 규칙에 맞게 계산해야 한다.

국렬이는 세 번씩이나 같은 형식의 수식을 줬고, 국렬이, 참가자, 검수진 모두가 파싱으로부터 고통받는 것을 원하지 않기에 수식 형태를 바꿨다. 이번 입력으로 주어지는 수식은 수와 연산자가 번갈아 가면서 나오며 수와 연산자 사이에 띄어쓰기가 있다. 수식의 $i$번째 수를 $X_i$, $i$번째 연산자를 $Op_i$로 표시하면 수가 $N$개인 식을 $X_1$ $Op_1$ $X_2$ $Op_2$ ... $Op_{N-1}$ $X_N$로 표기할 수 있다. 연산자의 종류는 +, -, *, /가 있다. 마지막에 연산자가 있는 경우와 $X_i$가 음수인 경우, 앞에 불필요한 $0$이 있는 경우는 입력으로 주어지지 않는다. 즉, $-1-1$, $2+-3$, $001+0002$ 같은 경우는 입력으로 주어지지 않는다.

$N$개의 수로 이루어진 수식과 $N-1$ 개의 양의 정수 $u_i$가 주어진다. 다음 규칙에 맞게 계산할 것이다.

1. 다음을 $N-1$번 반복한다.
2. 가장 최근에 계산한 결과값을 기약분수 $P/Q$로 표현했을 때, $Q$의 $10^9+7$에 대한 곱셈 역원 $Q^{-1}$에 대해 $P \times Q^{-1}$을 $10^9+7$로 나눈 나머지를 $v$라고 하자. 이전에 계산한 결과값이 없는 경우 $v=0$이다.
3. $(u_i \oplus v)$ 번째 연산자를 계산하고, 이 때의 결과값을 출력한다. 여기서 $\oplus$는 bitwise XOR를 의미한다.
4. 계산한 연산자와 피연산자를 제거하고, 그 자리에 결과값을 넣는다.

예를 들어서 수식 $3 - 2 \times 5 + 10$과 양의 정수 $u = [1,3,14]$가 주어지면 다음과 같이 계산한다.

1. $1 \oplus 0 = 1$이기에 1번째 연산자를 계산한다. 이에 대한 결과값은 $3-2=1$로 $1$을 출력한 뒤에 수식은 $1 \times 5 + 10$이 된다.
2. $3 \oplus 1 = 2$이기에 2번째 연산자를 계산한다. 이에 대한 결과값은 $5+10 =15$로 $15$을 출력한 뒤에 수식은 $1 \times 15$가 된다.
3. $14 \oplus 15 = 1$이기에 1번째 연산자를 계산한다. 이에 대한 결과값은 $1 \times 15 =15$로 $15$을 출력한다.

이 문제에서의 나눗셈은 실수 나눗셈으로 생각한다. 즉, $5/2$는 $2$가 아닌 $2.5$다.

이처럼 수식을 계산하는 프로그램을 짜보자.

첫 번째 줄에 피연산자의 개수인 $N$이 주어진다. ($2 \le N \le 500\,000$)

두 번째 줄에 피연산자와 +, -, *, /로만 이루어진 수식이 주어진다. 피연산자와 연산자는 공백으로 구분해서 주어지며, 피연산자는 $0$ 이상 $10^9+6$ 이하의 정수다.

세 번째 줄에 $u_1$, ..., $u_{N-1}$이 공백으로 구분되어 주어진다. ($1 \le u_i \oplus v \le N - i$)

계산 과정 중에 $0$으로 나누는 경우는 주어지지 않는다.

각 $i$번째 줄에 $u_i$에 대한 결과 값을 기약분수 $P/Q$로 표현했을 때, $Q$의 $10^9+7$에 대한 곱셈 역원 $Q^{-1}$에 대해 $P \times Q^{-1}$을 $10^9+7$로 나눈 나머지를 출력한다.