description: Denote a cyclic sequence of size n as an array s such that s_n is adjacent to s_1. The segment s[r, l] where l < r is the concatenation of s[r, n] and s[1, l].
  
  You are given an array a consisting of n integers. Define b as the cyclic sequence obtained from concatenating m copies of a. Note that b has size n ⋅ m.
  
  You are given an integer k where k = 1 or k is a prime number. Find the number of different segments in b where the sum of elements in the segment is divisible by k.
  
  Two segments are considered different if the set of indices of the segments are different. For example, when n = 3 and m = 2, the set of indices for segment s[2, 5] is \{2, 3, 4, 5\}, and for segment s[5, 2] is \{5, 6, 1, 2\}. In particular, the segments s[1, 6], s[2,1], …, s[6, 5] are considered as the same segment.
  
  Output the answer modulo 10^9 + 7.
  
  Input
  
  The first line contains three integers n, m, and k (1 ≤ n, m, k ≤ 2 ⋅ 10^5, k = 1 or k is a prime number).
  
  The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 2 ⋅ 10^5).
  
  Output
  
  Output an integer denoting the number of different segments in b where the sum of elements in the segment is divisible by k, modulo 10^9 + 7.
  
  Examples
  
  Input
  
  
  5 1 5
  1 2 3 4 3
  
  
  Output
  
  
  4
  
  
  Input
  
  
  5 1 5
  1 2 3 4 5
  
  
  Output
  
  
  5
  
  
  Input
  
  
  5 4 5
  1 2 3 4 5
  
  
  Output
  
  
  125
  
  Note
  
  In the first example, all valid segments are [1,4], [2, 3], [3, 5], and [4, 2].
  
  In the second example, one of the valid segments is [1, 5].
solution: #include <bits/stdc++.h>
  using namespace std;
  const int N = 210000;
  const int M = 1100000;
  const int mod = 1e9 + 7;
  const int inf = (int)1e9;
  const double eps = 1e-9;
  namespace Poly {
  const int BASE = 20;
  const int MAXN = 1 << BASE;
  const int BRUTEL = 128;
  const int mod = 1000000007;
  int pow_mod(int a, long long e) {
    int res = 1;
    for (; e; a = (long long)a * a % mod, e >>= 1)
      if (e & 1) res = (long long)res * a % mod;
    return res;
  }
  int pow_mod(int a, long long e, int mod) {
    int res = 1;
    for (; e; a = (long long)a * a % mod, e >>= 1)
      if (e & 1) res = (long long)res * a % mod;
    return res;
  }
  int modsqr(int a, int n) {
    int b, k, i, x;
    if (n == 2) return a % n;
    if (pow_mod(a, (n - 1) / 2, n) == 1) {
      if (n % 4 == 3)
        x = pow_mod(a, (n + 1) / 4, n);
      else {
        for (b = 1; pow_mod(b, (n - 1) / 2, n) == 1; b++)
          ;
        i = (n - 1) / 2;
        k = 0;
        do {
          i /= 2;
          k /= 2;
          if ((pow_mod(a, i, n) * (long long)pow_mod(b, k, n) + 1) % n == 0)
            k += (n - 1) / 2;
        } while (i % 2 == 0);
        x = (pow_mod(a, (i + 1) / 2, n) * (long long)pow_mod(b, k / 2, n)) % n;
      }
      if (x * 2 > n) x = n - x;
      return x;
    }
    return -1;
  }
  const double PI = acos(-1.0);
  struct complex {
    double r, i;
    complex(double _r = 0.0, double _i = 0.0) {
      r = _r;
      i = _i;
    }
    complex operator+(const complex &b) { return complex(r + b.r, i + b.i); }
    complex operator-(const complex &b) { return complex(r - b.r, i - b.i); }
    complex operator*(const complex &b) {
      return complex(r * b.r - i * b.i, r * b.i + i * b.r);
    }
    complex conj() { return complex(r, -i); }
  };
  complex W[2][MAXN * 2];
  void init() {
    for (int h = 2; h <= MAXN; h <<= 1)
      for (int d = 0; d < h / 2; d++) {
        W[0][h + d] = complex(cos(2 * d * PI / h), sin(2 * d * PI / h));
        W[1][h + d] = complex(cos(-2 * d * PI / h), sin(-2 * d * PI / h));
      }
  }
  void change(complex y[], int len) {
    int i, j, k;
    for (i = 1, j = len / 2; i < len - 1; i++) {
      if (i < j) swap(y[i], y[j]);
      k = len / 2;
      while (j >= k) {
        j -= k;
        k /= 2;
      }
      if (j < k) j += k;
    }
  }
  void fft(complex y[], int len, int type) {
    change(y, len);
    for (int h = 2; h <= len; h <<= 1)
      for (int j = 0; j < len; j += h)
        for (int k = j, d = 0; k < j + h / 2; k++, d++) {
          complex w;
          if (type == 1)
            w = W[0][h + d];
          else
            w = W[1][h + d];
          complex u = y[k], t = w * y[k + h / 2];
          y[k] = u + t;
          y[k + h / 2] = u - t;
        }
    if (type == -1)
      for (int i = 0; i < len; i++) y[i].r /= len;
  }
  template <class T>
  struct poly {
    T *a;
    int length, size;
    void clear() {
      delete[] a;
      a = nullptr;
      size = length = 0;
    }
    void apply(int size) {
      if (!size) return;
      a = new T[size]();
      this->size = size;
    }
    void resize(int size) {
      if (!size) return;
      T *aux = a;
      a = new T[size]();
      memcpy(a, aux, sizeof(T) * (length + 1));
      if (this->size) delete[] aux;
      this->size = size;
    }
    void initpoly(const poly &p, int length) {
      clear();
      apply(length + 1);
      memcpy(a, p.a, sizeof(T) * (std::min(length, p.length) + 1));
      this->length = length;
    }
    void print() {
      for (int i = 0; i <= length; i++) {
        printf("%d", a[i]);
        if (i != length)
          printf(" ");
        else
          printf("\n");
      }
    }
    void setlength(int length) {
      if (length >= size) resize(length + 1);
      if (length >= this->length) {
        this->length = length;
        return;
      }
      memset(a + length + 1, 0, sizeof(T) * (this->length - length));
      this->length = length;
    }
    void reverse() { std::reverse(a, a + length + 1); }
    poly() : a(nullptr), length(-1), size(0) {}
    poly(int length) : a(nullptr), length(length) { apply(length + 1); }
    poly(const poly &p) : a(nullptr) { initpoly(p, p.length); }
    poly(const poly &p, int length) : a(nullptr) { initpoly(p, length); }
    poly(T p[], int n) {
      apply(n + 2 << 1);
      length = n;
      memcpy(a, p, sizeof(T) * (n + 1));
    }
    ~poly() { clear(); }
    inline T add(const T &a, const T &b) const { return (a + b) % mod; }
    inline T sub(const T &a, const T &b) const { return (a - b + mod) % mod; }
    inline T mul(const T &a, const T &b) const { return (long long)a * b % mod; }
    inline T mod_inv(const T &a) const { return pow_mod(a, mod - 2); }
    T value(T x) {
      T res = 0, now = 1;
      for (int i = 0; i <= length; i++) {
        res = add(res, mul(a[i], now));
        now = mul(now, x);
      }
      return res;
    }
    T &operator[](int pos) { return a[pos]; }
    poly &operator=(const poly &p) {
      if (&p != this) initpoly(p, p.length);
      return *this;
    }
    poly operator<<(const int &dis) const {
      poly res(length + dis);
      memcpy(res.a + dis, a, sizeof(T) * (length + 1));
      return res;
    }
    poly operator>>(const int &dis) const {
      if (dis > length) return poly(-1);
      poly res(length - dis);
      memcpy(res.a, a + dis, sizeof(T) * (res.length + 1));
      return res;
    }
    poly operator+(const poly &p) const {
      if (length == -1) return p;
      if (p.length == -1) return *this;
      poly res(*this, std::max(length, p.length));
      for (int i = 0; i <= p.length; i++) res.a[i] = add(res.a[i], p.a[i]);
      return res;
    }
    poly operator-(const poly &p) const {
      if (length == -1) return p;
      if (p.length == -1) return *this;
      poly res(*this, std::max(length, p.length));
      for (int i = 0; i <= p.length; i++) res.a[i] = sub(res.a[i], p.a[i]);
      return res;
    }
    poly operator-() const {
      poly res(length);
      for (int i = 0; i <= length; i++) res[i] = sub(0, a[i]);
      return res;
    }
    poly operator*(const T &p) const {
      poly res(length);
      for (int i = 0; i <= length; i++) res[i] = mul(a[i], p);
      return res;
    }
    poly operator+(const T &p) const {
      poly res(length);
      for (int i = 0; i <= length; i++) res[i] = add(a[i], p);
      return res;
    }
    poly operator-(const T &p) const {
      poly res(length);
      for (int i = 0; i <= length; i++) res[i] = sub(a[i], p);
      return res;
    }
    void mul(T *a, T *b, T *c, int lengtha, int lengthb, int lengthret,
             int n) const {
      for (int i = 0; i <= n; i++) c[i] = 0;
      for (int i = 0; i <= lengtha; i++)
        for (int j = 0; j <= std::min(lengthb, n - i); j++)
          c[i + j] = add(c[i + j], mul(a[i], b[j]));
    }
    void merge_fft(complex *a, complex *b, int lengthret, int type) const {
      for (int i = 0; i < lengthret; i++) a[i] = a[i] + complex(0, 1.0) * b[i];
      fft(a, lengthret, type);
      b[0] = a[0].conj();
      for (int i = 1; i < lengthret; i++) b[i] = a[lengthret - i].conj();
      for (int i = 0; i < lengthret; i++) {
        complex cur_c = a[i], cur_d = b[i];
        a[i] = (cur_c + cur_d) * complex(0.5, 0);
        b[i] = (cur_c - cur_d) * complex(0, -0.5);
      }
    }
    void conv(T *a, T *b, T *c, int lengtha, int lengthb, int lengthret,
              int n) const {
      if (n < BRUTEL) {
        mul(a, b, c, lengtha, lengthb, lengthret, n);
        return;
      }
      complex *ka = new complex[lengthret];
      complex *kb = new complex[lengthret];
      complex *ra = new complex[lengthret];
      complex *rb = new complex[lengthret];
      const int s = 1 << 15;
      for (int i = 0; i < lengthret; i++) {
        ka[i] = i > lengtha ? 0 : a[i] / s;
        ra[i] = i > lengtha ? 0 : a[i] % s;
        kb[i] = i > lengthb ? 0 : b[i] / s;
        rb[i] = i > lengthb ? 0 : b[i] % s;
      }
      merge_fft(ka, ra, lengthret, 1);
      merge_fft(kb, rb, lengthret, 1);
      for (int i = 0; i < lengthret; i++) {
        complex cur_ka = ka[i], cur_kb = kb[i];
        complex cur_ra = ra[i], cur_rb = rb[i];
        ka[i] = cur_ka * cur_kb;
        kb[i] = cur_ka * cur_rb + cur_ra * cur_kb;
        ra[i] = cur_ra * cur_rb;
      }
      fft(ka, lengthret, -1);
      fft(kb, lengthret, -1);
      fft(ra, lengthret, -1);
      for (int i = 0; i <= n; i++)
        c[i] = ((long long)(ka[i].r + 0.5) % mod * (long long)s * s +
                (long long)(kb[i].r + 0.5) % mod * (long long)s +
                (long long)(ra[i].r + 0.5)) %
               mod;
      delete[] ka;
      delete[] ra;
      delete[] kb;
      delete[] rb;
    }
    poly operator*(const poly &p) const {
      if (length == -1 || p.length == -1) return poly(-1);
      int n = length + p.length;
      int lengthret = 1;
      for (; lengthret <= n; lengthret <<= 1)
        ;
      poly res(n);
      conv(a, p.a, res.a, length, p.length, lengthret, n);
      return res;
    }
    poly czt(T c, int m) {
      int n = m + length;
      int lengthret = 1;
      for (; lengthret <= n; lengthret <<= 1)
        ;
      T *a1 = new T[lengthret];
      T *a2 = new T[lengthret];
      T *a3 = new T[lengthret];
      T *w[3];
      w[0] = new T[lengthret];
      w[1] = new T[lengthret];
      w[2] = new T[lengthret];
      w[0][0] = 1, w[0][1] = c, w[1][0] = w[1][1] = w[2][0] = w[2][1] = 1;
      for (int i = 2; i < lengthret; i++) {
        w[0][i] = mul(w[0][i - 1], c);
        w[1][i] = mul(w[0][i - 1], w[1][i - 1]);
        w[2][i] = mod_inv(w[1][i]);
      }
      for (int i = 0; i < lengthret; i++) {
        a1[i] = w[1][i];
        a2[i] = i > length ? 0 : mul(w[2][i], a[i]);
      }
      delete[] w[0];
      delete[] w[1];
      reverse(a1, a1 + lengthret);
      poly res(m);
      conv(a1, a2, a3, lengthret - 1, lengthret - 1, lengthret, lengthret - 1);
      for (int i = 0; i <= m; i++) res[i] = mul(a3[lengthret - 1 - i], w[2][i]);
      delete[] a1;
      delete[] a2;
      delete[] a3;
      delete[] w[2];
      return res;
    }
    friend poly operator-(const T &q, const poly &p) { return p - q; }
    friend poly operator+(const T &q, const poly &p) { return p + q; }
    friend poly operator*(const T &q, const poly &p) { return p * q; }
    poly &operator+=(const poly &p) {
      *this = *this + p;
      return *this;
    }
    poly &operator-=(const poly &p) {
      *this = *this - p;
      return *this;
    }
    poly &operator*=(const poly &p) {
      *this = *this * p;
      return *this;
    }
    poly &operator*=(const T &p) {
      *this = *this * p;
      return *this;
    }
    poly der() const {
      if (length == -1) return poly(-1);
      poly res(length - 1);
      for (int i = 0; i < length; i++) res[i] = mul(a[i + 1], i + 1);
      return res;
    }
    poly integral() const {
      int *a1 = new int[length + 3];
      a1[0] = 0, a1[1] = 1;
      for (int i = 2; i <= length + 1; i++)
        a1[i] = sub(0, mul(mod / i, a1[mod % i]));
      poly res(length + 1);
      for (int i = length + 1; i; i--) res[i] = mul(a[i - 1], a1[i]);
      delete[] a1;
      return res;
    }
    poly inv(int n) const {
      poly res(1);
      res[0] = pow_mod(a[0], mod - 2);
      int len = 1;
      while (len < n) len *= 2;
      for (int degree = 0; degree < len;) {
        degree = degree << 1 | 1;
        poly a1(*this, degree), a2(res);
        res *= res, res.setlength(degree);
        a1 *= res, a1.setlength(degree);
        res = 2 * a2 - a1;
      }
      res.setlength(n - 1);
      return res;
    }
    poly operator/(const poly &p) const {
      if (p.length > length) return poly(-1);
      poly a(*this), b(p);
      a.reverse(), a.setlength(length - p.length + 1);
      b.reverse(), b.setlength(length - p.length + 1);
      poly res(b.inv(length - p.length + 1));
      res *= a;
      res.setlength(length - p.length);
      res.reverse();
      return res;
    }
    poly operator%(const poly &p) const {
      poly res = (*this) - (*this) / p * p;
      res.setlength(p.length - 1);
      return res;
    }
    poly &operator/=(const poly &p) {
      *this = *this / p;
      return *this;
    }
    poly &operator%=(const poly &p) {
      *this = *this % p;
      return *this;
    }
    poly ln(int n) const {
      poly res = (*this).der() * (*this).inv(n);
      res.setlength(n);
      res = res.integral();
      res.setlength(n - 1);
      return res;
    }
    poly sqrt(int n) const {
      poly res(1);
      res[0] = modsqr(a[0], mod);
      for (int degree = 0; degree < n;) {
        degree = degree << 1 | 1;
        poly a1(*this, degree), a2(res);
        res = res * res + a1, res.setlength(degree);
        a2 = (a2 * 2).inv(degree + 1);
        res = res * a2;
        res.setlength(degree);
      }
      res.setlength(n - 1);
      return res;
    }
    poly exp(int n) const {
      poly res(1);
      res[0] = 1;
      poly unit(res);
      for (int degree = 0; degree < n;) {
        degree = degree << 1 | 1;
        poly a1(*this, degree), a2(res);
        a1 = unit - a2.ln(degree + 1) + a1;
        a1.setlength(degree);
        res = a1 * a2;
        res.setlength(degree);
      }
      res.setlength(n - 1);
      return res;
    }
    poly pow(int n, T k1, T k2 = -1, T k3 = -1) const {
      if (k2 == -1) k2 = k1;
      if (k3 == -1) k3 = k1;
      int pos = -1;
      for (int i = 0; i <= length; i++)
        if (a[i] != 0) {
          pos = i;
          break;
        }
      if (pos == -1) return (*this);
      poly res = (*this) >> pos;
      T coef = res[0], inverse = mod_inv(res[0]);
      res = res * inverse;
      res = res.ln(n);
      res = res * k1;
      res = res.exp(n);
      pos = min((long long)pos * (long long)k3, (long long)n);
      res = (res * pow_mod(coef, k2)) << pos;
      res.setlength(n - 1);
      return res;
    }
    poly sin(int n) const {
      static T i = modsqr(mod - 1, mod);
      poly a1 = ((*this) * i).exp(n);
      poly a2 = ((*this) * sub(0, i)).exp(n);
      poly res = a1 - a2;
      res = res * mod_inv(mul(2, i));
      return res;
    }
    poly cos(int n) const {
      static T i = modsqr(mod - 1, mod);
      poly a1 = ((*this) * i).exp(n);
      poly a2 = ((*this) * sub(0, i)).exp(n);
      poly res = a1 + a2;
      res = res * mod_inv(2);
      return res;
    }
    poly arcsin(int n) const {
      poly res(1);
      res[0] = 1;
      poly unit(res);
      poly a1 = (*this).der();
      poly a2 = (*this) * (*this);
      a2.setlength(n - 1);
      a2 = unit - a2;
      a2 = a2.sqrt(n);
      a1 = a1 * a2.inv(n);
      a1.setlength(n - 1);
      res = a1.integral();
      res.setlength(n - 1);
      return res;
    }
    poly arccos(int n) const {
      poly res(1);
      res[0] = 1;
      poly unit(res);
      poly a1 = (*this).der();
      poly a2 = (*this) * (*this);
      a2.setlength(n - 1);
      a2 = unit - a2;
      a2 = a2.sqrt(n);
      a1 = -a1 * a2.inv(n);
      a1.setlength(n - 1);
      res = a1.integral();
      res.setlength(n - 1);
      return res;
    }
    poly arctan(int n) const {
      poly res(1);
      res[0] = 1;
      poly unit(res);
      poly a1 = (*this).der();
      poly a2 = (*this) * (*this);
      a2.setlength(n - 1);
      a2 = unit + a2;
      a1 = a1 * a2.inv(n);
      a1.setlength(n - 1);
      res = a1.integral();
      res.setlength(n - 1);
      return res;
    }
    void multi_eval(T b[], int m) {
      int M = 4 * m;
      poly *moder = new poly[M];
      poly *rem = new poly[M];
      int *l = new int[M];
      int *r = new int[M];
      memset(l, 0, sizeof(int) * (M));
      memset(r, 0, sizeof(int) * (M));
      l[1] = 1, r[1] = m;
      for (int i = 1; i < M; i++) {
        if (l[i] == r[i]) continue;
        int mid = (l[i] + r[i]) / 2;
        l[i << 1] = l[i], r[i << 1] = mid;
        l[i << 1 | 1] = mid + 1, r[i << 1 | 1] = r[i];
      }
      for (int i = M - 1; i; i--) {
        if (l[i] == r[i]) {
          if (l[i]) {
            moder[i] = poly(1), moder[i][0] = sub(0, b[l[i]]), moder[i][1] = 1;
          }
          continue;
        }
        moder[i] = moder[i << 1] * moder[i << 1 | 1];
        moder[i].setlength(r[i] - l[i] + 1);
      }
      rem[1] = (*this) % moder[1];
      for (int i = 1; i < M; i++) {
        if (l[i] == r[i]) continue;
        rem[i << 1] = rem[i] % moder[i << 1];
        rem[i << 1 | 1] = rem[i] % moder[i << 1 | 1];
      }
      for (int i = 1; i < M; i++)
        if (l[i] && l[i] == r[i]) b[l[i]] = rem[i][0];
      delete[] l;
      delete[] r;
      delete[] rem;
      delete[] moder;
    }
    void fast_lagrange(T x[], T y[], int m) {
      int M = 4 * m;
      poly *moder = new poly[M];
      poly *res = new poly[M];
      int *l = new int[M];
      int *r = new int[M];
      T *val = new T[M];
      memset(l, 0, sizeof(int) * (M));
      memset(r, 0, sizeof(int) * (M));
      l[1] = 1, r[1] = m;
      for (int i = 1; i < M; i++) {
        if (l[i] == r[i]) continue;
        int mid = (l[i] + r[i]) / 2;
        l[i << 1] = l[i], r[i << 1] = mid;
        l[i << 1 | 1] = mid + 1, r[i << 1 | 1] = r[i];
      }
      for (int i = M - 1; i; i--) {
        if (l[i] == r[i]) {
          if (l[i]) {
            moder[i] = poly(1), moder[i][0] = sub(0, x[l[i]]), moder[i][1] = 1;
          }
          continue;
        }
        moder[i] = moder[i << 1] * moder[i << 1 | 1];
        moder[i].setlength(r[i] - l[i] + 1);
      }
      for (int i = 1; i <= m; i++) val[i] = x[i];
      poly g = moder[1].der();
      g.multi_eval(val, m);
      for (int i = M - 1; i; i--) {
        if (l[i] == r[i]) {
          if (l[i]) {
            res[i] = poly(0), res[i][0] = mul(y[l[i]], mod_inv(val[l[i]]));
          }
          continue;
        }
        res[i] =
            res[i << 1] * moder[i << 1 | 1] + res[i << 1 | 1] * moder[i << 1];
        res[i].setlength(r[i] - l[i]);
      }
      (*this) = res[1];
      delete[] l;
      delete[] r;
      delete[] moder;
      delete[] res;
    }
  };
  }  // namespace Poly
  int n, m, k, a[N], sum[N], psum[N];
  Poly::poly<int> f1, f2;
  long long b[N], ans;
  int num[N];
  int main() {
    Poly::init();
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ;
    cin >> n >> m >> k;
    f1.setlength(k - 1), f2.setlength(k - 1);
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      sum[i] = (sum[i - 1] + a[i]) % k;
      f1[sum[i]] += 1;
    }
    for (int i = 0; i <= m - 2; i++) {
      int rem = (long long)i * (long long)sum[n] % k;
      f2[rem] = (f2[rem] + m - (i + 2) + 1) % mod;
    }
    f1 = f1 * f2;
    for (int i = 0; i <= f1.length; i++) {
      b[i % k] = (b[i % k] + f1[i]) % mod;
    }
    int all = (long long)m * (long long)sum[n] % k;
    psum[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
      psum[i] = (psum[i + 1] + a[i]) % k;
    }
    for (int i = 1; i <= n; i++) {
      ans = (ans + b[(k - psum[i]) % k]) % mod;
      ans = (ans + b[(all - psum[i] + k) % k]) % mod;
    }
    if (m > 1) {
      ans = (ans - 1 + mod) % mod;
    }
    for (int i = 1; i <= n; i++) {
      num[sum[i - 1]]++;
      ans = (ans + (long long)m * num[sum[i]]) % mod;
    }
    memset(num, 0, sizeof(num));
    for (int i = 1; i <= n; i++) num[psum[i]]++;
    for (int i = 2; i <= m; i++) {
      int rem = (long long)(i - 1) * sum[n] % k;
      ans = (ans - num[(all + k - rem) % k] + mod) % mod;
    }
    memset(num, 0, sizeof(num));
    for (int i = 1; i <= n; i++) num[sum[i]]++;
    for (int i = 2; i <= m; i++) {
      int rem = (long long)(i - 1) * sum[n] % k;
      ans = (ans - num[(all + k - rem) % k] + mod) % mod;
    }
    if (m > 1) ans = (ans + 2 + mod) % mod;
    memset(num, 0, sizeof(num));
    if (n > 1 || m > 1) {
      for (int i = 2; i <= n; i++) {
        num[sum[i - 1]]++;
        int delta = m;
        if (i == n) delta--;
        ans = (ans + (long long)delta * num[(sum[i] - all + k) % k]) % mod;
      }
      if (m > 1) {
        for (int i = 1; i <= n; i++) {
          long long delta = m - 1;
          if (i == n) delta--;
          if (sum[i] == all) ans = (ans + delta) % mod;
        }
      }
    }
    cout << ans << endl;
    return 0;
  }
  