# Bedao propose 2022/11/30

Cho một dãy gồm $n$ số nguyên dương $a_1,a_2,\dots a_n$ và một số nguyên dương $k$.

Xét một tập hợp $S$ gồm $k$ phần tử $b_1, b_2,\dots, b_k$, ta định nghĩa $f(S)=\prod_{i=1}^k b_i$.

Xét một dãy con gồm các phần tử từ $l$ đến $r$, ta định nghĩa $g(l,r)=\sum_{S_k\subset a[l\dots r]} f(S_k)$ trong đó $a[l\dots r]$ là dãy con liên tiếp của $a$ gồm các phần tử từ $l$ đến $r$ và $S_k$ là một tập hợp gồm $k$ phần tử.

Cho $q$ truy vấn thuộc $2$ loại:

- $1$ $l$ $r$: in ra giá trị của $g(l,r)$ lấy phần dư cho $10^9+7$
- $2$ $i$ $x$: cập nhập lại $a_i=x$

Giới hạn:

- $1\leq n \leq 10^5$
- $1\leq a_i,x \leq 10^9$
- $1\leq k \leq 20$
- $1\leq q \leq 10^5$