22976번 - 계산 최적화 서브태스크

현욱은 덧셈과 곱셈을 계산할 수 있는 간단한 계산 장치를 만들었다. 이 계산 장치는 처음에 값 $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 \le N, Q \le 1000 $

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

$1 \le N, Q \le 50000 $

추가 제한 없음