시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB146595271.233%

문제

현욱은 덧셈과 곱셈을 계산할 수 있는 간단한 계산 장치를 만들었다. 이 계산 장치는 처음에 값 $0$에서 시작해서 $N$($1 \le N \le 5 \cdot 10^5 $)번의 연산을 순서대로 수행한 결과값을 반환한다. 연산은 아래의 두 종류가 있다.

  • + k : 이전 값에 $k$를 더한다($ 1 \le k \le 10^9 $)
  • * k : 이전 값에 $k$를 곱한다($ 1 \le k \le 10^9 $)

연산 결과값이 아주 커질 수 있기 때문에 이 계산 장치는 항상 계산 결과값을 $10^9+7$로 나눈 나머지를 저장한다.

현욱은 이 계산 장치에서 일부 연산을 변경한 후 계산 결과가 어떻게 달라지는지를 확인하고 싶다. 현욱은 총 $Q$($1 \le Q \le 5 \cdot 10^5 $)번 계산 장치의 연산을 변경할 예정이며, 연산 변경은 다음과 같은 형태로 주어진다.

  • i + k : $i$번째 연산을 이전 값에 $k$를 더하는 연산으로 변경한다($ 1 \le i \le N, 1 \le k \le 10^9 $).
  • i * k : $i$번째 연산을 이전 값에 $k$를 곱하는 연산으로 변경한다($ 1 \le i \le N, 1 \le k \le 10^9 $).

모든 변경 사항은 누적된다.

현욱은 연산 변경이 하나 일어날 때마다 다시 처음부터 계산을 하는게 너무 비효율적이라고 생각한다. 현욱을 도와 현욱의 계산 장치를 최적화해서, 연산 변경이 일어날 때 결과를 빠르게 다시 계산하는 프로그램을 작성해보자.

입력

첫줄에 연산의 개수 $N$과 연산을 변경할 횟수 $Q$가 공백으로 구분되어 주어진다($1 \le N, Q \le 5 \cdot 10^5 $).

둘째 줄부터 $N$줄에 걸쳐 맨 처음 계산 장치를 구성하는 $N$개의 연산이 순서대로 주어진다.

그 다음부터 $Q$줄에 걸쳐 계산 장치의 연산을 어떻게 변경했는지 정보가 순서대로 주어진다.

출력

$Q$줄에 걸쳐 연산이 바뀔 때마다 계산 장치의 계산 결과값이 어떻게 바뀌는지 출력한다.

서브태스크 1 (23점)

$1 \le N, Q \le 1000 $

서브태스크 2 (15점)

항상 모든 곱셈 연산은 모든 덧셈 연산보다 뒤에 나온다.

서브태스크 3 (32점)

$1 \le N, Q \le 50000 $

서브태스크 4 (55점)

추가 제한 없음

예제 입력 1

6 10
+ 3
* 2
+ 2
* 3
+ 4
* 5
1 + 2
3 * 1
4 * 5
2 + 6
2 * 2
1 * 2
3 * 1
4 + 4
1 + 5
3 * 4

예제 출력 1

110
80
120
220
120
20
20
40
90
240

출처

Contest > 소프트콘 > 제3회 소프트콘 D번

채점 및 기타 정보

  • 예제는 채점하지 않는다.