Subtask 1: Trong Subtask này, ta giả sử ~\{b_1,b_2,...,b_{r-l+1}\} = \{a_l, a_{l+1},...a_r\}~. Sử dụng quy hoặch động như sau:

~f(i, j) =~ Tổng giá trị của các dãy con kích thước ~j~ của ~\{b_1,b_2,...,b_i\}~

Dễ dàng nhận thấy ~f(0,0)=1~. Khi đó có hai trường hợp xảy ra:

• Tổng các dãy không chứa ~b_i~ là ~f(i-1,j)~
• Tổng các dãy chứa ~b_i~ là ~f(i-1,j)\times b_i~

~\Rightarrow~ ~f(i, j) = f(i - 1, j) + f(i - 1, j - 1) \times b_i~

Subtask 2: Trong Subtask này, ta cũng vẫn giả sử ~\{b_1,b_2,...,b_{r-l+1}\} = \{a_l, a_{l+1},...a_r\}~. Ta có ~b_i\le 2~, gọi số lượng ~b_i = 2~ là ~x~; ta suy ra tổng giá trị các dãy độ dài ~k~ là:

~\sum_{i=0}^{\min(k,x)} C_x^i\times2^i \times C_{(r-l+1)-x}^{k-i}\times 1^{k-i}~

Subtask 3: Xét hai dãy ~x=\{x_1,x_2,...,x_m\}~, ~y=\{y_1,y_2,...,y_n\}~ và dãy ~z=\{x_1,x_2,...,x_m,y_1,...,y_n\}~. Gọi:

• ~f_x(k)=~ Tổng giá trị các dãy con kích thước ~k~ của ~x~
• ~f_y(k)=~ Tổng giá trị các dãy con kích thước ~k~ của ~y~
• ~f_z(k)=~ Tổng giá trị các dãy con kích thước ~k~ của ~z~

Khi đó ta có khẳng định:

~f_z(K)=\sum_{k=0}^K f_x(k)\times f_y(K-k)~

Vậy, ta sẽ sử dụng một cây phân đoạn (Segment Tree) để lưu trữ hàm mục tiêu. Trên một node ~id~ quản lí đoạn ~[l, r]~ sẽ lưu mục mảng hàm mục tiêu cho đoạn con ~a[l..r]~ tương ứng.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define FF first
#define SS second
#define eps 1e-9
#define PI aocs(-1.0)
// VECTOR (6)
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
#define ub upper_bound
#define uniq(x) sort(all((x))), (x).resize(unique(all((x))) - (x).begin());
// BIT (6)
#define BIT(x, i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define SUBSET(big, small) (((big)&(small))==(small))
#define FIRSTBIT(x) __builtin_ctzll(x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, ll> ii;

/* */
template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
/* */

/* CODE BELOW */
const int N = 1e5 + 7, M = 1e9 + 7;
const int MOD = 1e9 + 7;
const int oo = 1e9 + 7;

const int K = 20 + 1;

int n, q, k;

int add(int a, int b) {
    a+= b; if(a>= MOD) a-=MOD;
    return a;
}

void upd(int &a, int b) {
    a+= b; if(a>=MOD) a-=MOD;
}

int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

struct Node {
    int _dp[K];
    Node() {
        for(int i = 0; i < K; i++) {
            _dp[i] = 0;
        }
    }
    int &operator[] (int index) {
        return _dp[index];
    }
    const int &operator[] (int index) const {
        return _dp[index];
    }
};


Node add(const Node &l, const Node &r) {
    Node ans;
    for(int i=1;i<=k;i++) {
        for(int j=0;j<i;j++) {
            upd(ans[i], mul(l[j], r[i-j]));
        }
        upd(ans[i], add(l[i], r[i]));
    }
    return ans;
}

class SegmentTree {
private:
    int n;
    vector<Node> st;
private:
    void update(int idx, int l0, int r0, int p, int v) {
        if(l0 > r0 || p < l0 || p > r0) return;
        if(l0 == p && r0 == p) {
            st[idx][1] = v;
            return;
        }
        int mid = (l0+r0)/2;
        update(idx*2, l0, mid, p, v);
        update(idx*2+1, mid+1, r0, p, v);

        st[idx] = add(st[idx * 2], st[idx * 2 + 1]);
    }
    Node query(int idx, int l0, int r0, int l, int r) {
        if(l0 > r0 || r < l0 || l > r0) return Node();
        if(l <= l0 && r0 <= r) {
            return st[idx];
        }
        int mid = (l0 + r0)/2;
        Node a = query(idx * 2, l0, mid, l, r);
        Node b = query(idx * 2 + 1, mid + 1, r0, l, r);
        return add(a, b);
    }
public:
    SegmentTree(int _n = 0):n(_n) {
        st.assign(4 * _n + 7, Node());
    }
    void update(int p, int v) {
        update(1, 1, n, p, v);
    }
    int query(int l, int r) {
        return query(1, 1, n, l, r)[k];
    }
};

SegmentTree IT;

signed main() {
    fastIO;
    cin >> n >> k;
    IT = SegmentTree(n);
    for(int i=1;i<=n;i++) {
        int v; cin >> v;
        IT.update(i, v);
    }

    cin >> q;
    for(int i=1;i<=q;i++) {
        int type; cin >> type;
        if(type == 1) {
            int l, r;
            cin >> l >> r;
            cout << IT.query(l, r) << endl;
        } else {
            int idx, x;
            cin >> idx >> x;
            IT.update(idx, x);
        }
    }


    return 0;
}