#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000007;
static const double eps = 1e-8;
template <class T>
inline T MIN(const T x, const T y) {
  return (x < y) ? x : y;
}
template <class T>
inline T MAX(const T x, const T y) {
  return (x > y) ? x : y;
}
template <class T>
inline void UPDMIN(T &x, const T y) {
  if (x > y) x = y;
}
template <class T>
inline void UPDMAX(T &x, const T y) {
  if (x < y) x = y;
}
template <class T>
inline int SIZE(const T &x) {
  return (int)x.size();
}
template <class T>
inline int LENGTH(const T &x) {
  return (int)x.length();
}
template <class T1, class T2>
inline pair<T1, T2> MP(const T1 &x, const T2 &y) {
  return make_pair(x, y);
}
inline int BINT(const int x) { return 1 << x; }
inline long long BLLD(const int x) { return 1LL << x; }
inline int BINT_TEST(const int s, const int x) { return (s & BINT(x)) != 0; }
inline int BLLD_TEST(const long long s, const int x) {
  return (s & BLLD(x)) != 0LL;
}
template <class T>
inline T LOWBIT(const T x) {
  return (x ^ (x - 1)) & x;
}
template <class T>
inline int BITCOUNT(const T x) {
  return (!x) ? x : (1 + BITCOUNT(x & (x - 1)));
}
const double PI = acos(-1.0);
const double EPS = 1e-5;
template <class T>
inline T SQR(const T x) {
  return x * x;
}
template <class T1, class T2>
inline T1 POW(const T1 x, const T2 y) {
  if (!y)
    return 1;
  else if ((y & 1) == 0) {
    return SQR(POW(x, y >> 1));
  } else
    return POW(x, y ^ 1) * x;
}
template <class T>
inline T GCD(const T x, const T y) {
  if (x < 0) return GCD(-x, y);
  if (y < 0) return GCD(x, -y);
  return (!y) ? x : GCD(y, x % y);
}
template <class T>
inline T LCM(const T x, const T y) {
  if (x < 0) return LCM(-x, y);
  if (y < 0) return LCM(x, -y);
  return x * (y / GCD(x, y));
}
template <class T>
inline T EEA(const T a, const T b, T &x, T &y) {
  if (a < 0) {
    T d = EEA(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = EEA(a, -b, x, y);
    y = -y;
    return d;
  }
  if (!b) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = EEA(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <class T>
inline vector<pair<T, int> > FACTORIZE(T x) {
  vector<pair<T, int> > ret;
  if (x < 0) x = -x;
  for (T i = 2; x > 1;) {
    if (x % i == 0) {
      int count = 0;
      for (; x % i == 0; x /= i) count++;
      ret.push_back(MP(i, count));
    }
    i++;
    if (i > x / i) i = x;
  }
  return ret;
}
template <class T>
inline int ISPRIME(const T x) {
  if (x <= 1) return 0;
  for (T i = 2; SQR(i) <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
template <class T>
inline T EULARFUNCTION(T x) {
  vector<pair<T, int> > f = FACTORIZE(x);
  for (typename vector<pair<T, int> >::iterator it = f.begin(); it != f.end();
       it++) {
    x = x / it->first * (it->first - 1);
  }
  return x;
}
template <class T>
inline T INVERSEE(const T a, const T b = MOD) {
  T x, y;
  EEA(a, b, x, y);
  return x ? x : 1;
}
int *PRIMELIST(const int til, int *length = NULL) {
  int *foo = (int *)malloc(sizeof(int) * (til + 1));
  int len = 0;
  memset(foo, 0, sizeof(int) * (til + 1));
  for (int i = 2; i <= til; i++) {
    if (!foo[i]) foo[len++] = i;
    for (int j = 0; j < len && foo[j] <= til / i; j++) {
      foo[foo[j] * i] = 1;
      if (i % foo[j] == 0) break;
    }
  }
  if (length != NULL) {
    *length = len;
  }
  foo[len++] = 0;
  foo = (int *)realloc(foo, sizeof(int) * len);
  return foo;
}
template <class T>
inline T MOD_STD(const T x, const T m = MOD) {
  return (x % m + m) % m;
}
template <class T>
inline void MOD_STD(T *x, const T m = MOD) {
  *x = (*x % m + m) % m;
}
template <class T>
inline T MOD_ADD(const T x, const T y, const T m = MOD) {
  return (x + y) % m;
}
template <class T>
inline void MOD_ADD(T *x, const T y, const T m = MOD) {
  *x = (*x + y) % m;
}
template <class T>
inline T MOD_MUL(const T x, const T y, const T m = MOD) {
  return (T)((1LL * x * y) % m);
}
template <class T>
inline void MOD_MUL(T *x, const T y, const T m = MOD) {
  *x = (T)((1LL * (*x) * y) % m);
}
template <class T1, class T2>
inline T1 MOD_POW(const T1 x, const T2 y, const T1 m = MOD) {
  if (y == 0)
    return 1 % m;
  else if ((y & 1) == 0) {
    T1 z = MOD_POW(x, y >> 1, m);
    return MOD_MUL(z, z, m);
  } else
    return MOD_MUL(MOD_POW(x, y ^ 1, m), x, m);
}
inline long long MODL_MUL(long long x, long long y, const long long m = MOD) {
  MOD_STD(&x, m);
  MOD_STD(&y, m);
  if (x < y) swap(x, y);
  long long z = 0LL;
  while (y > 0) {
    if (y & 1) {
      MOD_ADD(&z, x, m);
    }
    MOD_ADD(&x, x, m);
    y >>= 1;
  }
  return z;
}
inline long long MODL_POW(const long long x, const long long y,
                          const long long m = MOD) {
  if (y == 0LL)
    return 1LL % m;
  else if ((y & 1) == 0LL) {
    long long z = MODL_POW(x, y >> 1, m);
    return MODL_MUL(z, z, m);
  } else
    return MODL_MUL(MODL_POW(x, y ^ 1, m), x, m);
}
template <class T>
class cycleq_t {
 private:
  size_t cnt, cap;
  size_t lef, rig;
  T *que;

 public:
  cycleq_t(const size_t size) {
    this->cap = size;
    this->que = (T *)malloc(sizeof(T) * size);
    this->clear();
  }
  ~cycleq_t() { free(this->que); }
  inline void clear() {
    this->lef = this->rig = 0;
    this->cnt = 0;
  }
  inline void put(const T &obj) {
    assert(this->cnt < this->cap);
    this->que[this->rig++] = obj;
    if (this->rig == this->cap) this->rig = 0;
    this->cnt++;
  }
  inline void put_back(const T &obj) { this->put(obj); }
  inline void put_front(const T &obj) {
    assert(this->cnt < this->cap);
    this->lef--;
    if (!~this->lef) this->lef = this->cap - 1;
    this->que[this->lef] = obj;
    this->cnt++;
  }
  inline T pop() {
    assert(this->cnt > 0);
    T res = this->que[this->lef++];
    if (this->lef == this->cap) this->lef = 0;
    this->cnt--;
    return res;
  }
  inline T pop_front() { return this->pop(); }
  inline T pop_back() {
    assert(this->cnt > 0);
    this->rig--;
    if (!~this->rig) this->rig = this->cap - 1;
    this->cnt--;
    return this->que[this->rig];
  }
  inline T get(int64_t offset = 0) {
    if (offset >= 0) {
      assert(offset < this->cnt);
      offset += this->lef;
      if (offset > this->cap) offset -= this->cap;
      return this->que[offset];
    } else {
      assert(offset >= -this->cnt);
      offset += this->rig;
      if (offset < 0) offset += this->cap;
      return this->que[offset];
    }
  }
};
template <class T>
class MATX {
 private:
  unsigned long hig, wid;
  T *data;
  void __init() {
    this->data = (T *)malloc(sizeof(T) * this->hig * this->wid);
    memset(this->data, 0, sizeof(T) * this->hig * this->wid);
  }

 public:
  MATX() {
    this->hig = this->wid = 1;
    __init();
  }
  MATX(const unsigned long _len) {
    this->hig = this->wid = _len;
    __init();
  }
  MATX(const unsigned long _hig, const unsigned long _wid) {
    this->hig = _hig;
    this->wid = _wid;
    __init();
  }
  MATX(const MATX &rhs) {
    this->hig = rhs.hig;
    this->wid = rhs.wid;
    this->data = (T *)malloc(sizeof(T) * this->hig * this->wid);
    for (unsigned long x = 0; x < this->hig; x++)
      for (unsigned long y = 0; y < this->wid; y++)
        this->data[x * this->wid + y] = rhs.at(x, y);
  }
  ~MATX() { free(this->data); }
  T &operator()(const unsigned long x, const unsigned long y) {
    if (x >= this->hig || y >= this->wid) return (*(T *)NULL);
    return this->data[x * this->wid + y];
  }
  T *operator[](const unsigned long x) {
    if (x >= this->hig) return (T *)NULL;
    return this->data + (x * this->wid);
  }
  MATX &operator=(const MATX &rhs) {
    if (this->hig != rhs.hig || this->wid != rhs.wid) {
      free(this->data);
      this->hig = rhs.hig;
      this->wid = rhs.wid;
      this->data = (T *)malloc(sizeof(T) * this->hig * this->wid);
    }
    for (unsigned long x = 0; x < this->hig; x++)
      for (unsigned long y = 0; y < this->wid; y++)
        this->data[x * this->wid + y] = rhs.at(x, y);
    return *this;
  }
  const MATX operator+(const MATX &opn) const {
    MATX ret(*this);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        ret.data[x * ret.wid + y] += opn.at(x, y);
    return ret;
  }
  const MATX operator-(const MATX &opn) const {
    MATX ret(*this);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        ret.data[x * ret.wid + y] -= opn.at(x, y);
    return ret;
  }
  const MATX operator*(const MATX &opn) const {
    MATX ret(this->hig, opn.wid);
    const unsigned long len = MIN(this->wid, opn.hig);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        for (unsigned long z = 0; z < len; z++)
          ret.data[x * ret.wid + y] += this->at(x, z) * opn.at(z, y);
    return ret;
  }
  const MATX mul(const MATX &opn) const { return *this * opn; }
  template <class T2>
  const MATX mul(const MATX &opn, const T2 m) const {
    MATX ret(this->hig, opn.wid);
    const unsigned long len = MIN(this->wid, opn.wid);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        for (unsigned long z = 0; z < len; z++)
          MOD_ADD(&ret.data[x * ret.wid + y],
                  MOD_MUL(this->at(x, z), opn.at(z, y), m), m);
    return ret;
  }
  MATX &operator+=(const MATX &rhs) {
    *this = *this + rhs;
    return *this;
  }
  MATX &operator-=(const MATX &rhs) {
    *this = *this - rhs;
    return *this;
  }
  MATX &operator*=(const MATX &rhs) {
    *this = *this * rhs;
    return *this;
  }
  const MATX pow(const unsigned long p) const {
    MATX buff(*this), ret(this->hig, this->wid);
    ret.set_one();
    if (p > 0)
      for (unsigned long i = 1;; i <<= 1) {
        if (p & i) ret *= buff;
        buff *= buff;
        if (i > (p >> 1)) break;
      }
    return ret;
  }
  template <class T2>
  const MATX pow(const unsigned long p, const T2 m) const {
    MATX buff(*this), ret(this->hig, this->wid);
    ret.set_one();
    if (p > 0)
      for (unsigned long i = 1;; i <<= 1) {
        if (p & i) ret = ret.mul(buff, m);
        buff = buff.mul(buff, m);
        if (i > (p >> 1)) break;
      }
    return ret;
  }
  const T at(const unsigned long x, const unsigned long y) const {
    if (x >= this->hig || y >= this->wid) return 0;
    return this->data[x * wid + y];
  }
  void show() const {
    for (unsigned long x = 0; x < this->hig; x++) {
      for (unsigned long y = 0; y < this->wid; y++)
        cout << this->at(x, y) << " ";
      cout << endl;
    }
  }
  void set_one() {
    for (unsigned long x = 0; x < this->hig; x++)
      for (unsigned long y = 0; y < this->wid; y++)
        this->data[x * this->wid + y] = (x == y) ? 1 : 0;
  }
};
template <class T>
class complex_t {
 public:
  T r, i;
  complex_t(T x = 0.0, T y = 0.0) {
    this->r = x;
    this->i = y;
  }
  complex_t operator+(const complex_t &opn) const {
    return complex_t(this->r + opn.r, this->i + opn.i);
  }
  complex_t operator-(const complex_t &opn) const {
    return complex_t(this->r - opn.r, this->i - opn.i);
  }
  complex_t operator*(const complex_t &opn) const {
    return complex_t(this->r * opn.r - this->i * opn.i,
                     this->r * opn.i + this->i * opn.r);
  }
};
template <class T>
void fast_fourier_trans(complex_t<T> f[], const int len, const int is_dft) {
  for (int i = 1, j = len >> 1; i < len - 1; i++) {
    if (i < j) swap(f[i], f[j]);
    int k = len >> 1;
    while (j >= k) {
      j -= k;
      k >>= 1;
    }
    if (j < k) j += k;
  }
  for (int h = 2; h <= len; h <<= 1) {
    complex_t<T> wn(cos(is_dft ? (-2 * PI / h) : (2 * PI / h)),
                    sin(is_dft ? (-2 * PI / h) : (2 * PI / h)));
    for (int i = 0; i < len; i += h) {
      complex_t<T> wm(1.0, 0.0);
      for (int j = i; j < i + (h >> 1); j++) {
        complex_t<T> u = f[j];
        complex_t<T> t = wm * f[j + (h >> 1)];
        f[j] = u + t;
        f[j + (h >> 1)] = u - t;
        wm = wm * wn;
      }
    }
  }
  if (!is_dft) {
    for (int i = 0; i < len; i++) f[i].r /= len * 1.0;
  }
}
class MILLERRABIN {
 private:
  static const int prime_table[12];
  int witness(long long a, long long d, long long s, long long n) {
    long long r = MODL_POW(a, d, n);
    if (r == 1 || r == n - 1) return 0;
    for (int i = 0; i < s - 1; i++) {
      r = MODL_MUL(r, r, n);
      if (r == 1) return 1;
      if (r == n - 1) return 0;
    }
    return 1;
  }

 public:
  int test(const long long n) {
    if (n <= 2LL) return 0;
    long long p = n - 1LL, s = 0LL;
    while (!(p & 1)) {
      p >>= 1;
      s++;
    }
    for (int i = 0; i < 12 && this->prime_table[i] < n; i++) {
      if (witness(this->prime_table[i], p, s, n)) return 0;
    }
    return 1;
  }
};
const int MILLERRABIN::prime_table[12] = {2,  3,  5,  7,  11, 13,
                                          17, 19, 23, 29, 31, 37};
template <class T>
inline int fsign(const T x) {
  if (x > -eps && x < eps) return 0;
  return (x < 0.0) ? -1 : 1;
}
template <class T>
class point_t {
 public:
  T x, y;
  point_t() {
    this->x = 0.0;
    this->y = 0.0;
  }
  point_t(const T _x, const T _y) {
    this->x = _x;
    this->y = _y;
  }
  point_t operator-(const point_t &rhs) const {
    return point_t(this->x - rhs.x, this->y - rhs.y);
  }
  T operator^(const point_t &rhs) const {
    return this->x * rhs.y - this->y * rhs.x;
  }
  T operator*(const point_t &rhs) const {
    return this->x * rhs.x + this->y * rhs.y;
  }
  bool operator<(const point_t &rhs) const {
    if (fsign(this->y - rhs.y) != 0) return fsign(this->y - rhs.y) < 0;
    return fsign(this->x - rhs.x) < 0;
  }
  T cross(const point_t &p, const point_t &q) const {
    return (p - *this) ^ (q - *this);
  }
  void rotate(const double radian) {
    T x0 = x, y0 = y;
    T sinr = sin(radian);
    T cosr = cos(radian);
    x = x0 * cosr - y0 * sinr;
    y = x0 * sinr + y0 * cosr;
  }
  void rotate(const point_t &p, const double radian) {
    T x0 = x - p.x, y0 = y - p.y;
    T sinr = sin(radian);
    T cosr = cos(radian);
    x = x0 * cosr - y0 * sinr + p.x;
    y = x0 * sinr + y0 * cosr + p.y;
  }
  T dist2(const point_t &lhs, const point_t &rhs) const {
    return (lhs - rhs) * (lhs - rhs);
  }
  T dist2(const point_t &rhs) const { return (*this - rhs) * (*this - rhs); }
  T dist(const point_t &lhs, const point_t &rhs) const {
    return sqrt((lhs - rhs) * (lhs - rhs));
  }
  T dist(const point_t &rhs) const {
    return sqrt((*this - rhs) * (*this - rhs));
  }
};
template <class T>
class segment_t {
 public:
  point_t<T> p, q;
  segment_t() {
    this->p.x = this->p.y = 0.0;
    this->q.x = this->q.y = 0.0;
  }
  template <class T2>
  segment_t(const point_t<T2> &_p, const point_t<T2> &_q) {
    this->p.x = _p.x;
    this->p.y = _p.y;
    this->q.x = _q.x;
    this->q.y = _q.y;
  }
  segment_t(const T px, const T py, const T qx, const T qy) {
    this->p.x = px;
    this->p.y = py;
    this->q.x = qx;
    this->q.y = qy;
  }
  T length() const { return this->p.dist(this->q); }
  T length2() const { return this->p.dist2(this->q); }
  int contain(const point_t<T> &pnt, const int ignore_endpoint = 0) const {
    if (ignore_endpoint) {
      return fsign((this->p - pnt) ^ (this->q - pnt)) == 0 &&
             fsign((pnt.x - this->p.x) * (pnt.x - this->q.x)) < 0 &&
             fsign((pnt.y - this->p.y) * (pnt.y - this->q.y)) < 0;
    } else {
      return fsign((this->p - pnt) ^ (this->q - pnt)) == 0 &&
             fsign((pnt.x - this->p.x) * (pnt.x - this->q.x)) <= 0 &&
             fsign((pnt.y - this->p.y) * (pnt.y - this->q.y)) <= 0;
    }
  }
  int intersection(const segment_t &sa, const segment_t &sb,
                   const int ignore_endpoint = 0) const {
    if (!ignore_endpoint) {
      if (sa.contain(sb.p) || sa.contain(sb.q) || sb.contain(sa.p) ||
          sb.contain(sa.q))
        return 1;
    }
    return fsign(sa.p.cross(sa.q, sb.p)) * fsign(sa.p.cross(sa.q, sb.q)) < 0 &&
           fsign(sb.p.cross(sb.q, sa.p)) * fsign(sb.p.cross(sb.q, sa.q)) < 0;
  }
  int intersection(const segment_t &rhs, const int ignore_endpoint = 0) const {
    return this->intersection(*this, rhs, ignore_endpoint);
  }
};
template <class T>
static int compare_pas(const void *x, const void *y, void *z) {
  const point_t<T> *p1 = (point_t<T> *)x;
  const point_t<T> *p2 = (point_t<T> *)y;
  const point_t<T> *p0 = (point_t<T> *)z;
  int sgn = fsign(((*p1) - (*p0)) ^ ((*p2) - (*p0)));
  if (sgn != 0) return -sgn;
  return fsign(p0->dist2(*p1) - p0->dist2(*p2));
}
template <class T>
void polar_angle_sort(point_t<T> *pnts, const int n) {
  int p = 0;
  for (int i = 1; i < n; i++) {
    if (pnts[p] < pnts[i]) p = i;
  }
  swap(pnts[0], pnts[p]);
  qsort_r(pnts + 1, n - 1, sizeof(point_t<T>), compare_pas<T>, pnts);
}
template <class T>
void graham(point_t<T> *pnts, const int n, int *idx, int &m) {
  polar_angle_sort(pnts, n);
  m = 0;
  if (n < 3) return;
  idx[m++] = 0;
  idx[m++] = 1;
  for (int i = 2; i < n; i++) {
    while (m > 1 &&
           fsign(pnts[idx[m - 2]].cross(pnts[idx[m - 1]], pnts[i])) <= 0)
      m--;
    idx[m++] = i;
  }
}
class bipartite_matching_c {
 private:
  size_t capl, capr, cape;
  size_t cnte;
  struct bm_edge_t;
  struct bm_left_node_t {
    bm_edge_t *head;
    int flag;
  } * leftnodes;
  struct bm_right_node_t {
    bm_left_node_t *partner;
  } * rightnodes;
  struct bm_edge_t {
    bm_right_node_t *right;
    bm_edge_t *next;
  } * edgepool, *edgetail;
  int augmented(bm_left_node_t *node, const int flag) {
    node->flag = flag;
    for (bm_edge_t *edge = node->head; edge != NULL; edge = edge->next) {
      if (edge->right->partner == NULL ||
          (edge->right->partner->flag < flag &&
           augmented(edge->right->partner, flag))) {
        edge->right->partner = node;
        return 1;
      }
    }
    return 0;
  }

 public:
  bipartite_matching_c(const size_t numl, const size_t numr,
                       const size_t nume) {
    this->capl = numl;
    this->leftnodes =
        (bm_left_node_t *)malloc(sizeof(bm_left_node_t) * this->capl);
    this->capr = numr;
    this->rightnodes =
        (bm_right_node_t *)malloc(sizeof(bm_right_node_t) * this->capr);
    this->cape = nume;
    this->edgepool = (bm_edge_t *)malloc(sizeof(bm_edge_t) * this->cape);
    this->reset();
  }
  ~bipartite_matching_c() {
    free(this->leftnodes);
    free(this->rightnodes);
    free(this->edgepool);
  }
  void reset() {
    for (size_t i = 0; i < this->capl; i++) {
      this->leftnodes[i].head = NULL;
    }
    this->edgetail = this->edgepool;
    this->cnte = 0;
  }
  void add_edge(const size_t u, const size_t v) {
    assert(u < this->capl || v < this->capr);
    assert(this->cnte < this->cape);
    this->edgetail->next = this->leftnodes[u].head;
    this->edgetail->right = &this->rightnodes[v];
    this->leftnodes[u].head = this->edgetail++;
    this->cnte++;
  }
  int maximum_matching() {
    for (size_t i = 0; i < this->capl; i++) {
      this->leftnodes[i].flag = -1;
    }
    for (size_t i = 0; i < this->capr; i++) {
      this->rightnodes[i].partner = NULL;
    }
    int foo = 0;
    for (size_t u = 0; u < this->capl; u++) {
      if (this->leftnodes[u].head == NULL) continue;
      if (augmented(&this->leftnodes[u], u)) foo++;
    }
    return foo;
  }
};
template <class T>
class maxflow_c {
 private:
  size_t capv, cape;
  size_t cntv, cnte;
  struct mf_edge_t;
  struct mf_vertex_t {
    mf_edge_t *head, *hold;
    size_t idx, hig;
  } * vertex, **vhead, **vtail, **vque;
  struct mf_edge_t {
    mf_vertex_t *src, *dst;
    mf_edge_t *nxt, *rsv;
    T cap, cur;
  } * edge_pool, *edge_tail, **esup;
  struct dncnode_t {
    mf_vertex_t *vtx;
    T precap, reflux;
  } * dinic_stack_pool;
  size_t *dcnt;
  size_t higlev(size_t src, size_t trm, const int reverse = 0) {
    if (reverse) swap(src, trm);
    if (this->vque == NULL)
      this->vque = (mf_vertex_t **)malloc(sizeof(mf_vertex_t *) * this->capv);
    size_t lef = 0, rig = 0;
    for (mf_vertex_t **vtxp = this->vhead; vtxp != this->vtail; vtxp++)
      (*vtxp)->hig = numeric_limits<size_t>::max();
    this->vertex[src].hig = 0;
    this->vque[rig++] = &this->vertex[src];
    this->vertex[trm].hig = numeric_limits<size_t>::max();
    for (; lef < rig; lef++) {
      mf_vertex_t *vtx = this->vque[lef];
      for (mf_edge_t *edge = vtx->head; edge != NULL; edge = edge->nxt) {
        if (!reverse) {
          if (edge->cur < edge->cap && edge->dst->hig > vtx->hig + 1) {
            edge->dst->hig = vtx->hig + 1;
            this->vque[rig++] = edge->dst;
          }
        } else {
          if (edge->rsv->cur < edge->rsv->cap &&
              edge->dst->hig > vtx->hig + 1) {
            edge->dst->hig = vtx->hig + 1;
            this->vque[rig++] = edge->dst;
          }
        }
      }
    }
    this->vque[rig++] = NULL;
    return this->vertex[trm].hig;
  }
  T isap_augment(const size_t src, const size_t trm) {
    T inc = numeric_limits<T>::max();
    for (size_t i = trm; i != src; i = this->esup[i]->src->idx) {
      UPDMIN(inc, this->esup[i]->cap - this->esup[i]->cur);
    }
    for (size_t i = trm; i != src; i = this->esup[i]->src->idx) {
      this->esup[i]->cur += inc;
      this->esup[i]->rsv->cur -= inc;
    }
    return inc;
  }
  size_t isap_retreat(size_t &i, const size_t src) {
    size_t best = numeric_limits<size_t>::max();
    for (mf_edge_t *edge = this->vertex[i].head; edge != NULL;
         edge = edge->nxt) {
      if (edge->cur < edge->cap) {
        UPDMIN(best, edge->dst->hig + 1);
      }
    }
    size_t rep = --this->dcnt[this->vertex[i].hig];
    this->vertex[i].hig = best;
    if (best < this->cntv) {
      this->dcnt[best]++;
    }
    if (i != src) i = this->esup[i]->src->idx;
    return rep;
  }

 public:
  maxflow_c(const size_t numv, const size_t nume) {
    this->capv = numv;
    this->cape = nume;
    this->vertex = (mf_vertex_t *)malloc(sizeof(mf_vertex_t) * numv);
    for (size_t i = 0; i < numv; i++) {
      this->vertex[i].idx = i;
    }
    this->vhead = (mf_vertex_t **)malloc(sizeof(mf_vertex_t *) * numv);
    this->vtail = this->vhead;
    this->vque = NULL;
    this->edge_pool = (mf_edge_t *)malloc(sizeof(mf_edge_t) * (nume << 1));
    this->dinic_stack_pool = NULL;
    this->esup = NULL;
    this->dcnt = NULL;
    this->reset();
  };
  ~maxflow_c() {
    if (this->dcnt != NULL) free(this->dcnt);
    if (this->esup != NULL) free(this->esup);
    if (this->dinic_stack_pool != NULL) free(this->dinic_stack_pool);
    free(this->edge_pool);
    if (this->vque != NULL) free(this->vque);
    free(this->vhead);
    free(this->vertex);
  }
  void reset() {
    for (size_t i = 0; i < this->capv; i++) this->vertex[i].head = NULL;
    this->vtail = this->vhead;
    this->edge_tail = this->edge_pool;
    this->cntv = 0;
    this->cnte = 0;
  }
  void add_edge(const size_t u, const size_t v, const T c, const T r = 0) {
    assert(u < this->capv && v < this->capv);
    assert(this->cnte < this->cape);
    this->edge_tail->nxt = this->vertex[u].head;
    this->edge_tail->rsv = this->edge_tail + 1;
    this->edge_tail->src = &this->vertex[u];
    this->edge_tail->dst = &this->vertex[v];
    this->edge_tail->cap = c;
    this->edge_tail->cur = 0;
    if (this->vertex[u].head == NULL) {
      *this->vtail++ = &this->vertex[u];
      this->cntv++;
    }
    this->vertex[u].head = this->edge_tail++;
    this->edge_tail->nxt = this->vertex[v].head;
    this->edge_tail->rsv = this->edge_tail - 1;
    this->edge_tail->src = &this->vertex[v];
    this->edge_tail->dst = &this->vertex[u];
    this->edge_tail->cap = r;
    this->edge_tail->cur = 0;
    if (this->vertex[v].head == NULL) {
      *this->vtail++ = &this->vertex[v];
      this->cntv++;
    }
    this->vertex[v].head = this->edge_tail++;
    this->cnte++;
  }
  T dinic(const size_t src, const size_t trm) {
    assert(src < this->capv && trm < this->capv && src != trm);
    T foo = 0;
    if (this->dinic_stack_pool == NULL)
      this->dinic_stack_pool =
          (dncnode_t *)malloc(sizeof(dncnode_t) * this->capv);
    while (higlev(src, trm) < numeric_limits<size_t>::max()) {
      for (size_t i = 0; this->vque[i] != NULL; i++) {
        this->vque[i]->hold = this->vque[i]->head;
      }
      dncnode_t *top = this->dinic_stack_pool;
      top->vtx = &this->vertex[src];
      top->precap = numeric_limits<T>::max();
      top->reflux = 0;
      while (this->vertex[src].hold != NULL) {
        if (top->vtx->idx != trm && top->vtx->hold != NULL &&
            top->vtx->hold->cur < top->vtx->hold->cap &&
            top->vtx->hold->src->hig + 1 == top->vtx->hold->dst->hig) {
          dncnode_t *prv = top++;
          top->vtx = prv->vtx->hold->dst;
          top->precap = MIN(prv->precap - prv->reflux,
                            prv->vtx->hold->cap - prv->vtx->hold->cur);
          top->reflux = 0;
        } else if (top->vtx->idx == trm) {
          T inc = top->precap;
          foo += inc;
          while (top->precap == top->reflux + inc) {
            inc += top->reflux;
            top--;
            top->vtx->hold->cur += inc;
            top->vtx->hold->rsv->cur -= inc;
          }
          top->reflux += inc;
        } else {
          if (top->vtx->hold == NULL) {
            T ref = top->reflux;
            top--;
            top->vtx->hold->cur += ref;
            top->vtx->hold->rsv->cur -= ref;
            top->reflux += ref;
          }
          top->vtx->hold = top->vtx->hold->nxt;
        }
      }
    }
    return foo;
  }
  T isap(const size_t src, const size_t trm) {
    assert(src < this->capv && trm < this->capv && src != trm);
    T foo = 0;
    if (higlev(src, trm, 1) < numeric_limits<size_t>::max()) {
      if (this->dcnt == NULL)
        this->dcnt = (size_t *)malloc(sizeof(size_t) * this->capv);
      if (this->esup == NULL)
        this->esup = (mf_edge_t **)malloc(sizeof(mf_edge_t *) * this->capv);
      for (size_t i = 0; i < this->cntv; i++) this->dcnt[i] = 0;
      for (size_t i = 0; this->vque[i] != NULL; i++) {
        this->vque[i]->hold = this->vque[i]->head;
        this->dcnt[this->vque[i]->hig]++;
      }
      size_t i = src;
      while (this->vertex[src].hig < this->cntv) {
        mf_edge_t *edge = this->vertex[i].hold;
        while (edge != NULL && !(edge->cur < edge->cap &&
                                 edge->src->hig == edge->dst->hig + 1)) {
          edge = edge->nxt;
        }
        if (edge != NULL) {
          this->vertex[i].hold = edge;
          this->esup[edge->dst->idx] = edge;
          i = edge->dst->idx;
          if (i == trm) {
            foo += isap_augment(src, trm);
            i = src;
          }
        } else {
          this->vertex[i].hold = this->vertex[i].head;
          if (isap_retreat(i, src) == 0) break;
        }
      }
    }
    return foo;
  }
};
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> r(m, 0);
  r[0] = 1;
  long long foo = 0LL;
  int presum = 0LL;
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    presum = (presum + x) % m;
    foo += r[presum] * 1LL;
    r[presum]++;
  }
  printf("%lld\n", foo);
  return 0;
}
