612. C

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC target("avx,avx2")

constexpr int INF = (int)1e9;
constexpr int N = (int)1e3 + 11;
constexpr int MAXN = (int)3000 + 11;
constexpr int md = (int)1e9+7;

vector<pair<int,int>> PrimeDivs[MAXN];
vector<int> divs[MAXN];

void rec(int i,int pos,int t = 1){
    if(pos >= PrimeDivs[i].size()){
        divs[i].pb(t);
        return;
    }
    rec(i,pos+1,t);
    for(int U = 1; U <= PrimeDivs[i][pos].second; U++){
        t *= PrimeDivs[i][pos].first;
        rec(i,pos+1,t);
    }
    return;
}

void add(int& a,int b){
    a += b;
    if(a >= md) a -= md;
}
void sub(int& a,int b){
    a -= b;
    if(a < 0) a += md;
}

int pw[MAXN];
int cnt[MAXN];
int sum[MAXN];
int subs[MAXN];
bool prime[MAXN];
int mobious[MAXN];

void ADD(int a){
    for(auto& x : divs[a])
        cnt[x]++;
}

void DEL(int a){
    for(auto& x : divs[a])
        cnt[x]--;
}

int get(){
    int ans = 0;
    for(int g = 1; g < MAXN; g++){
        int cur = 0;
        for(int i = g; i < MAXN; i += g){
            if(mobious[i/g] == 1)
                add(cur,pw[cnt[i]]-1);
            else if(mobious[i/g] == -1)
                sub(cur,pw[cnt[i]]-1);
        }
        ans = (ans + g*cur)%md;
    }
    return ans%md;
}

void solve(){
    pw[0] = 1;
    pw[1] = 2;
    for(int i = 2; i < MAXN; i++){
        pw[i] = (pw[i-1]*2)%md;
    }
    mobious[1] = 1;
    for(int i = 2; i < MAXN; i++)
        prime[i] = 1, mobious[i] = 1;
    for(int i = 2; i < MAXN; i++){
        if(!prime[i])
            continue;
        for(int j = i; j < MAXN; j+=i){
            int t = j;
            int cnt = 0;
            while(t % i == 0){
                t /= i;
                cnt++;
            }
            sum[j] += cnt;
            if(cnt > 1)
                mobious[j] = 0;
            PrimeDivs[j].pb(mp(i,cnt));
            if(i != j)
                prime[j] = false;
        }
    }

    divs[1].pb(1);

    for(int i = 2; i < MAXN; i++){
        int t = 1;
        rec(i,0);
        if(mobious[i] == 0)
            continue;
        if(sum[i] % 2 == 0)
            mobious[i] = 1;
        else
            mobious[i] = -1;
    }
}
    for(int i = 0; i < 20; i++){
        cout << mobious[i] << " ";
    }
    cout << "\n";
    return;

//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";

    /// PRECALCED divs

    int n,q;
    cin >> n >> q;

    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        ADD(x);
    }
//    return;

    cout << get() << "\n";

    for(int i = 0; i < q; i++){
        int tp,x;
        cin >> tp >> x;
        if(tp == 1)
            ADD(x);
        else
            DEL(x);
        cout << get() << "\n";
    }

    return;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    while(tests--){
        solve();
    }
}
/**

1 -1 -1 0 -1 1 -1

d[1] d[2] d[3] d[4] d[5]

1*(d[1]

**/