Problem: There are n players numbered from 0 to n-1 with ranks. The i-th player has rank i.

Players can form teams: the team should consist of three players and no pair of players in the team should have a conflict. The rank of the team is calculated using the following algorithm: let i, j, k be the ranks of players in the team and i < j < k, then the rank of the team is equal to A ⋅ i + B ⋅ j + C ⋅ k.

You are given information about the pairs of players who have a conflict. Calculate the total sum of ranks over all possible valid teams modulo 2^{64}.

Input

The first line contains two space-separated integers n and m (3 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ m ≤ 2 ⋅ 10^5) — the number of players and the number of conflicting pairs.

The second line contains three space-separated integers A, B and C (1 ≤ A, B, C ≤ 10^6) — coefficients for team rank calculation.

Each of the next m lines contains two space-separated integers u_i and v_i (0 ≤ u_i, v_i < n, u_i ≠ v_i) — pair of conflicting players.

It's guaranteed that each unordered pair of players appears in the input file no more than once.

Output

Print single integer — the total sum of ranks over all possible teams modulo 2^{64}.

Examples

Input

4 0
2 3 4


Output

64


Input

4 1
2 3 4
1 0


Output

38


Input

6 4
1 5 3
0 3
3 5
5 4
4 3


Output

164

Note

In the first example all 4 teams are valid, i.e. triples: {0, 1, 2}, {0, 1, 3}, {0, 2, 3} {1, 2, 3}.

In the second example teams are following: {0, 2, 3}, {1, 2, 3}.

In the third example teams are following: {0, 1, 2}, {0, 1, 4}, {0, 1, 5}, {0, 2, 4}, {0, 2, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
vector<int> adj[N];
int pos[N], dem[N], cnt[N], cnt1[N];
bool mark[N];
pair<int, int> edge_lis[N];
bitset<N> lis[640];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  unsigned long long n, i, ans = 0, a, b, c, m, j, k = 0, l, now = 0, damn, cac;
  cin >> n >> m >> a >> b >> c;
  l = sqrt(m);
  for (i = 1; i <= m; i++) {
    cin >> j >> k;
    j++;
    k++;
    edge_lis[i].first = j;
    edge_lis[i].second = k;
    adj[j].push_back(k);
    adj[k].push_back(j);
    if (j > k) {
      swap(j, k);
    }
    dem[j + 1]++;
    dem[k]--;
    cnt[k]++;
    cnt1[j]++;
  }
  for (i = 1; i <= n; i++) {
    sort(adj[i].begin(), adj[i].end());
    dem[i] += dem[i - 1];
    cnt[i] += cnt[i - 1];
  }
  for (i = n; i >= 1; i--) {
    cnt1[i] += cnt1[i + 1];
  }
  for (i = 1; i <= n; i++) {
    if (adj[i].size() > l) {
      now++;
      pos[i] = now;
      for (j = 0; j < adj[i].size(); j++) {
        lis[now].set(adj[i][j]);
      }
    }
    ans += (((i - 2) * (i - 1)) / 2) * c * (i - 1);
    ans += ((i - 1) * (n - i)) * b * (i - 1);
    ans += (((n - i) * (n - i - 1)) / 2) * a * (i - 1);
    damn = 0;
    ans -= c * cnt[i - 1] * (i - 1);
    ans -= b * dem[i] * (i - 1);
    ans -= a * cnt1[i + 1] * (i - 1);
    for (j = 0; j < adj[i].size(); j++) {
      if (adj[i][j] < i) {
        damn++;
        ans -= c * (i - 2) * (i - 1);
        ans -= b * (n - i) * (i - 1);
        cac = lower_bound(adj[adj[i][j]].begin(), adj[adj[i][j]].end(), i) -
              adj[adj[i][j]].begin();
        ans += c * cac * (i - 1);
        ans += b * (adj[adj[i][j]].size() - cac - 1) * (i - 1);
      } else {
        ans -= a * (n - i - 1) * (i - 1);
        ans -= b * (i - 1) * (i - 1);
        cac = lower_bound(adj[adj[i][j]].begin(), adj[adj[i][j]].end(), i) -
              adj[adj[i][j]].begin();
        ans += a * (adj[adj[i][j]].size() - cac - 1) * (i - 1);
        ans += b * cac * (i - 1);
      }
    }
    ans += ((damn * (damn - 1)) / 2) * c * (i - 1);
    ans +=
        ((adj[i].size() - damn) * (adj[i].size() - damn - 1) / 2) * a * (i - 1);
    ans += damn * (adj[i].size() - damn) * b * (i - 1);
  }
  for (i = 1; i <= n; i++) {
    if (pos[i]) {
      for (j = 1; j <= m; j++) {
        if (lis[pos[i]].test(edge_lis[j].first) &&
            lis[pos[i]].test(edge_lis[j].second)) {
          damn = 0;
          if (i > edge_lis[j].first) {
            damn++;
          }
          if (i > edge_lis[j].second) {
            damn++;
          }
          if (damn == 0) {
            ans -= (i - 1) * a;
          }
          if (damn == 1) {
            ans -= (i - 1) * b;
          }
          if (damn == 2) {
            ans -= (i - 1) * c;
          }
        }
      }
    } else {
      for (j = 0; j < adj[i].size(); j++) {
        if (pos[adj[i][j]]) {
          for (k = 0; k < j; k++) {
            if (lis[pos[adj[i][j]]].test(adj[i][k])) {
              damn = 0;
              if (i > adj[i][j]) {
                damn++;
              }
              if (i > adj[i][k]) {
                damn++;
              }
              if (damn == 0) {
                ans -= (i - 1) * a;
              }
              if (damn == 1) {
                ans -= (i - 1) * b;
              }
              if (damn == 2) {
                ans -= (i - 1) * c;
              }
            }
          }
        } else {
          for (k = 0; k < adj[adj[i][j]].size(); k++) {
            mark[adj[adj[i][j]][k]] = true;
          }
          for (k = 0; k < j; k++) {
            if (mark[adj[i][k]]) {
              damn = 0;
              if (i > adj[i][j]) {
                damn++;
              }
              if (i > adj[i][k]) {
                damn++;
              }
              if (damn == 0) {
                ans -= (i - 1) * a;
              }
              if (damn == 1) {
                ans -= (i - 1) * b;
              }
              if (damn == 2) {
                ans -= (i - 1) * c;
              }
            }
          }
          for (k = 0; k < adj[adj[i][j]].size(); k++) {
            mark[adj[adj[i][j]][k]] = false;
          }
        }
      }
    }
  }
  cout << ans;
}