Sum Over Subsets Codeforces Round #678 SOLUTION

You are given a multiset S. Over all pairs of subsets A and B, such that:

B⊂A;

|B|=|A|−1;

greatest common divisor of all elements in A is equal to one;

find the sum of ∑x∈Ax⋅∑x∈Bx, modulo 998244353.

Input

The first line contains one integer m (1≤m≤105): the number of different values in the multiset S.

Each of the next m lines contains two integers ai, freqi (1≤ai≤105,1≤freqi≤109). Element ai appears in the multiset S freqi times. All ai are different.

Output

Print the required sum, modulo 998244353.

Examples

inputCopy

2

1 1

2 1

outputCopy

9

inputCopy

4

1 1

2 1

3 1

6 1

outputCopy

1207

inputCopy

1

1 5

outputCopy

560

Note

A multiset is a set where elements are allowed to coincide. |X| is the cardinality of a set X, the number of elements in it.

A⊂B: Set A is a subset of a set B.

In the first example B={1},A={1,2} and B={2},A={1,2} have a product equal to 1⋅3+2⋅3=9. Other pairs of A and B don’t satisfy the given constraints.

#include <bits/stdc++.h>

 

using namespace std;

 

typedef long long ll;

typedef long double ld;

 

const int mod = (int) 1e9 + 7;

 

int pw(int a, int b) {

  int r = 1;

  while (b) {

    if (b & 1) {

      r = (ll) r * a % mod;

    }

    a = (ll) a * a % mod;

    b /= 2;

  }

  return r;

}

 

 

const int M = mod;

 

int add(int a, int b) {

  a += b;

  if (a >= M) return a – M;

  if (a < 0) return a + M;

  return a;

}

 

int mul(int a, int b) {

  return a * (ll) b % M;

}

 

int dv(int a, int b) {

  return mul(a, pw(b, M – 2));

}

 

int sqr(int x) {

  return mul(x, x);

}

 

const int N = (int) 2e5 + 7;

int f[N];

 

int c(int n, int k) {

  if (!(0 <= k && k <= n)) {

    assert(0);

  }

  return dv(f[n], mul(f[k], f[n – k]));

}

 

signed main() {

  ios::sync_with_stdio(0);

  cin.tie(0);

 

  ///freopen (“input”, “r”, stdin);

 

  f[0] = 1;

  for (int i = 1; i < N; i++) f[i] = mul(f[i – 1], i);

 

  int m;

  cin >> m;

  vector<int> a;

  for (int i = 1; i <= m; i++) {

    int x, f;

    cin >> x >> f;

    for (int j = 1; j <= f; j++) a.push_back(x);

  }

  int n = (int) a.size(), sol = 0;

  for (int m = 1; m < (1 << n); m++) {

    int g = 0;

    for (int i = 0; i < n; i++) if (m & (1 << i)) g = __gcd(g, a[i]);

    if (g == 1) {

      vector<int> e;

      int su = 0, cnt = 0;

      for (int i = 0; i < n; i++) {

        if (m & (1 << i)) {

          e.push_back(a[i]);

          su = add(su, a[i]);

          cnt++;

        }

      }

      sol = add(sol, mul(cnt – 1, sqr(su)));

    }

  }

  cout << sol << “n”;

}