#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 3e4 + 5;
const int maxm = 128, MAXM = maxm + 5;
const int mod = 10007;
const int inv2 = (mod + 1) / 2;

inline void add_mod(int &a, int b) {
    a += b;

    if (a >= mod)
        a -= mod;
}
inline int mod_add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}

inline ll pw(ll a, ll b) {
    ll res = 1;

    while (b) {
        if (b & 1)
            res = res * a % mod;

        a = a * a % mod;
        b >>= 1;
    }

    return res;
}

template<typename T>
struct Segment_Tree {
    static const int MAXP = MAXN * 2;
    T val[MAXP];
    int ls[MAXP], rs[MAXP], fa[MAXP], pcnt = 0;

    int build(int l, int r, int leaf[]) {
        if (l > r)
            return 0;

        int u = ++pcnt;
        ls[u] = rs[u] = fa[u] = 0;

        if (l == r) {
            leaf[l] = u;
            return u;
        }

        int mid = (l + r) >> 1;
        ls[u] = build(l, mid, leaf);
        rs[u] = build(mid + 1, r, leaf);
        fa[ls[u]] = fa[rs[u]] = u;
        return u;
    }
    void push_up_all(int u) {
        if (!ls[u])
            return;

        push_up_all(ls[u]);
        push_up_all(rs[u]);
        val[u].merge(val[ls[u]], val[rs[u]]);
    }
    void flush(int u) {
        while ((u = fa[u]) != 0)
            val[u].merge(val[ls[u]], val[rs[u]]);
    }
};

#define lowbit(x) ((x)&-(x))
int parity[MAXM];

int m;

struct Data1;
struct Data2;

struct Data1: array< array<int, 2>, maxm > {
    void set(int k) {
        for (int i = 0; i < m; ++i) {
            data()[i][0] = 0;
            data()[i][1] = parity[i & k] ? mod - 1 : 1;
        }
    }
    void merge(const Data1 &f, const Data1 &g) {
        for (int k = 0; k < m; ++k) {
            data()[k][0] = mod_add(f[k][0], g[k][0]);
            data()[k][1] = f[k][1] * g[k][1] % mod;
        }
    }
    void copy(const Data2 &);
};

struct Data2: array< array<int, 4>, maxm > {
    void merge(const Data2 &f, const Data2 &g) {
        for (int k = 0; k < m; ++k) {
            int *res = data()[k].data();
            const int *F = f.data()[k].data(), *G = g.data()[k].data();

            res[0] = (F[0] + G[0] + (F[1] + 1) * (G[2] + 1) - 1) % mod;
            res[1] = ((F[1] + 1) * G[3] + G[1]) % mod;
            res[2] = ((G[2] + 1) * F[3] + F[2]) % mod;
            res[3] = (F[3] * G[3]) % mod;
        }
    }
    void merge(const Data1 &f, const Data1 &g) {
        for (int k = 0; k < m; ++k) {
            int *res = data()[k].data();
            const int *F = f.data()[k].data(), *G = g.data()[k].data();

            res[0] = mod_add(F[0], G[0]);
            res[1] = res[2] = 0;
            res[3] = F[1] * G[1] % mod;
        }
    }
    void copy(const Data1 &);
};

void Data1::copy(const Data2 &f) {
    for (int k = 0; k < m; ++k) {
        int *res = data()[k].data();
        const int *F = f.data()[k].data();

        res[0] = (F[0] + F[1] + F[2] + F[3]) % mod;
        res[1] = (F[2] + F[3] + 1) % mod;
    }
}
void Data2::copy(const Data1 &f) {
    for (int k = 0; k < m; ++k) {
        int *res = data()[k].data();
        const int *F = f.data()[k].data();

        res[0] = F[0];
        res[1] = res[2] = 0;
        res[3] = F[1];
    }
}

vector<int> g[MAXN];

Data1 val[MAXN];
Segment_Tree<Data1> tree1;
Segment_Tree<Data2> tree2;

int rt1[MAXN], rt2[MAXN], pos1[MAXN], pos2[MAXN];
Data1 *ppos1[MAXN];
Data2 *ppos2[MAXN];

void upd_tree2(int u, bool needflush) {
    if (rt1[u])
        ppos2[u] -> merge(val[u], tree1.val[rt1[u]]);
    else
        ppos2[u] -> copy(val[u]);

    if (needflush)
        tree2.flush(pos2[u]);
}
void upd_tree1(int u, bool needflush) {
    if (pos1[u]) {
        ppos1[u] -> copy(tree2.val[rt2[u]]);

        if (needflush)
            tree1.flush(pos1[u]);
    }
}

int siz[MAXN], son[MAXN], anc[MAXN];
void dfs_tree(int u, int fa) {
    anc[u] = fa;
    siz[u] = 1;
    son[u] = 0;

    for (int v : g[u])
        if (v != fa) {
            dfs_tree(v, u);
            siz[u] += siz[v];

            if (son[u] == 0 || siz[v] > siz[son[u]])
                son[u] = v;
        }
}

int dfn[MAXN], seq[MAXN], top[MAXN], bot[MAXN], curdfn = 0;
void dfs_dfn(int u, int fa, int tp) {
    dfn[u] = ++curdfn;
    seq[curdfn] = u;
    top[u] = tp;
    bot[top[u]] = u;

    if (son[u])
        dfs_dfn(son[u], u, tp);

    vector<int> ch;

    for (int v : g[u])
        if (v != fa && v != son[u]) {
            dfs_dfn(v, u, v);
            ch.emplace_back(v);
        }

    static int leaf[MAXN];
    rt1[u] = tree1.build(0, (int)ch.size() - 1, leaf);

    for (int i = 0; i < (int)ch.size(); ++i) {
        pos1[ch[i]] = leaf[i];
        ppos1[ch[i]] = &tree1.val[leaf[i]];
        upd_tree1(ch[i], 0);
    }

    tree1.push_up_all(rt1[u]);

    if (u == tp) {
        int l = dfn[u], r = dfn[bot[u]];
        rt2[u] = tree2.build(l, r, leaf);

        for (int i = l; i <= r; ++i) {
            pos2[seq[i]] = leaf[i];
            ppos2[seq[i]] = &tree2.val[leaf[i]];
            upd_tree2(seq[i], 0);
        }

        tree2.push_up_all(rt2[u]);
    }
}

int main(void) {
    for (int i = 1; i < MAXM; ++i)
        parity[i] = parity[i ^ lowbit(i)] ^ 1;

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        val[i].set(x);
    }

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    dfs_tree(1, 0);
    dfs_dfn(1, 0, 1);

    ll ivm = pw(m, mod - 2);

    int Q;
    cin >> Q;

    while (Q--) {
        static char op[10];
        cin >> op;

        if (*op == 'C') {
            int u, k;
            cin >> u >> k;
            val[u].set(k);

            while (u) {
                upd_tree2(u, 1);
                u = top[u];
                upd_tree1(u, 1);
                u = anc[u];
            }
        } else {
            int k;
            cin >> k;

            const Data2 &f = tree2.val[rt2[1]];

            int ans = 0;

            for (int i = 0; i < m; ++i) {
                int cur = (f[i][0] + f[i][1] + f[i][2] + f[i][3]) % mod;

                if (parity[i & k])
                    cur = (mod - cur);

                add_mod(ans, cur);
            }

            ans = ans * ivm % mod;

            cout << ans << '\n';
        }
    }

    return 0;
}