#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000001;
template <class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &p) {
  return out << p.first << ' ' << p.second;
}
template <class T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  for (typeof((v).begin()) i = ((v).begin()); i != (v).end(); ++i) {
    out << *i << ' ';
  }
  return out;
}
template <class T, class U>
istream &operator>>(istream &in, pair<T, U> &p) {
  return in >> p.first >> p.second;
}
template <class T>
istream &operator>>(istream &in, vector<T> &v) {
  for (typeof((v).begin()) i = ((v).begin()); i != (v).end(); ++i) {
    in >> (*i);
  }
  return in;
}
template <class T>
ostream &operator,(ostream &out, const T &t) {
  return out << t;
}
template <class T>
istream &operator,(istream &in, T &t) {
  return in >> t;
}
int io_init() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout, fixed, setprecision(9);
  return 1;
}
int _io_dummy = io_init();
template <class T, class U>
bool remin(T &a, const U &b) {
  return b < a ? a = b, true : false;
}
template <class T, class U>
bool remax(T &a, const U &b) {
  return b > a ? a = b, true : false;
}
long long solve(int k, int b, const vector<int> &v) {
  long long ans = 0;
  if (!b) {
    int l = 0;
    for (typeof((v).begin()) i = ((v).begin()); i != (v).end(); ++i) {
      if (!*i) {
        ans += ++l;
      } else {
        l = 0;
      }
    }
    return ans;
  }
  if (b == k) ans = -solve(k, 0, v);
  b = (-b + k) % k;
  map<int, int> cnt;
  cnt[0] = 1;
  int s = 0;
  for (typeof((v).begin()) i = ((v).begin()); i != (v).end(); ++i) {
    s = (s + *i) % k;
    ans += cnt[(s + b) % k];
    ++cnt[s];
  }
  return ans;
}
int main() {
  int k, b, n;
  cin, k, b, n;
  vector<int> v(n);
  cin, v;
  cout, solve(k - 1, b, v), '\n';
}

### Prompt

Develop a solution in Cpp to the problem described below:

You know that the Martians use a number system with base k. Digit b (0 ≤ b < k) is considered lucky, as the first contact between the Martians and the Earthlings occurred in year b (by Martian chronology).

A digital root d(x) of number x is a number that consists of a single digit, resulting after cascading summing of all digits of number x. Word "cascading" means that if the first summing gives us a number that consists of several digits, then we sum up all digits again, and again, until we get a one digit number.

For example, d(35047) = d((3 + 5 + 0 + 4)7) = d(157) = d((1 + 5)7) = d(67) = 67. In this sample the calculations are performed in the 7-base notation.

If a number's digital root equals b, the Martians also call this number lucky.

You have string s, which consists of n digits in the k-base notation system. Your task is to find, how many distinct substrings of the given string are lucky numbers. Leading zeroes are permitted in the numbers.

Note that substring s[i... j] of the string s = a1a2... an (1 ≤ i ≤ j ≤ n) is the string aiai + 1... aj. Two substrings s[i1... j1] and s[i2... j2] of the string s are different if either i1 ≠ i2 or j1 ≠ j2.

Input

The first line contains three integers k, b and n (2 ≤ k ≤ 109, 0 ≤ b < k, 1 ≤ n ≤ 105).

The second line contains string s as a sequence of n integers, representing digits in the k-base notation: the i-th integer equals ai (0 ≤ ai < k) — the i-th digit of string s. The numbers in the lines are space-separated.

Output

Print a single integer — the number of substrings that are lucky numbers.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

10 5 6
3 2 0 5 6 1


Output

5

Input

7 6 4
3 5 0 4


Output

1

Input

257 0 3
0 0 256


Output

3

Note

In the first sample the following substrings have the sought digital root: s[1... 2] = "3 2", s[1... 3] = "3 2 0", s[3... 4] = "0 5", s[4... 4] = "5" and s[2... 6] = "2 0 5 6 1".

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000001;
template <class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &p) {
  return out << p.first << ' ' << p.second;
}
template <class T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  for (typeof((v).begin()) i = ((v).begin()); i != (v).end(); ++i) {
    out << *i << ' ';
  }
  return out;
}
template <class T, class U>
istream &operator>>(istream &in, pair<T, U> &p) {
  return in >> p.first >> p.second;
}
template <class T>
istream &operator>>(istream &in, vector<T> &v) {
  for (typeof((v).begin()) i = ((v).begin()); i != (v).end(); ++i) {
    in >> (*i);
  }
  return in;
}
template <class T>
ostream &operator,(ostream &out, const T &t) {
  return out << t;
}
template <class T>
istream &operator,(istream &in, T &t) {
  return in >> t;
}
int io_init() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout, fixed, setprecision(9);
  return 1;
}
int _io_dummy = io_init();
template <class T, class U>
bool remin(T &a, const U &b) {
  return b < a ? a = b, true : false;
}
template <class T, class U>
bool remax(T &a, const U &b) {
  return b > a ? a = b, true : false;
}
long long solve(int k, int b, const vector<int> &v) {
  long long ans = 0;
  if (!b) {
    int l = 0;
    for (typeof((v).begin()) i = ((v).begin()); i != (v).end(); ++i) {
      if (!*i) {
        ans += ++l;
      } else {
        l = 0;
      }
    }
    return ans;
  }
  if (b == k) ans = -solve(k, 0, v);
  b = (-b + k) % k;
  map<int, int> cnt;
  cnt[0] = 1;
  int s = 0;
  for (typeof((v).begin()) i = ((v).begin()); i != (v).end(); ++i) {
    s = (s + *i) % k;
    ans += cnt[(s + b) % k];
    ++cnt[s];
  }
  return ans;
}
int main() {
  int k, b, n;
  cin, k, b, n;
  vector<int> v(n);
  cin, v;
  cout, solve(k - 1, b, v), '\n';
}

```