구간 곱 구하기

$N$개의 수로 이루어진 수열이 있다. 이 수열은 중간에 원소가 자주 바뀌고, 그 사이사이에 어떤 구간의 곱을 구해야 한다.

예를 들어 수열이 1, 2, 3, 4, 5일 때 세 번째 수를 6으로 바꾸고 두 번째부터 다섯 번째까지의 곱을 구하면 240이다. 이어서 다섯 번째 수를 2로 바꾸고 세 번째부터 다섯 번째까지의 곱을 구하면 48이다.

수의 변경과 구간 곱 계산이 섞여서 주어질 때, 각 구간의 곱을 구하는 프로그램을 작성한다.

첫째 줄에 수의 개수 $N$($1 \le N \le 1{,}000{,}000$), 수를 바꾸는 횟수 $M$($1 \le M \le 10{,}000$), 구간의 곱을 구하는 횟수 $K$($1 \le K \le 10{,}000$)가 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에 수열의 원소가 한 줄에 하나씩 순서대로 주어진다.

이어지는 $M + K$개의 줄에는 세 정수 $a$, $b$, $c$가 주어진다. $a$가 1이면 $b$번째 수를 $c$로 바꾸고, $a$가 2이면 $b$번째 수부터 $c$번째 수까지의 곱을 구한다. $a$가 2인 줄에서는 $b \le c$이다.

입력으로 주어지는 모든 수는 0 이상 1,000,000 이하의 정수이다.

곱을 구하라는 질의마다 한 줄씩, 주어진 순서대로 모두 $K$줄을 출력한다. 각 줄에는 해당 구간의 곱을 1,000,000,007로 나눈 나머지를 출력한다.