#include <bits/stdc++.h>   typedef std::function<long long(long long)> fun;   class Map {     int n, w, r;     std::vector<int> A, B;     std::function<int(long long)> lower, upper;     std::vector<long long> who;     std::vector<int> val;     void find_array(std::vector<int> &a, const std::vector<long long> &S, fun f,                     fun g) {       a.resize(1 << r);       std::vector<std::list<long long> > set(1 << r);       std::vector<int> m(1 << (r + 1));       std::vector<int> ind;       for (long long x : S) {         if (set[f(x)].empty()) ind.push_back(f(x));         set[f(x)].push_back(x);       }       std::sort(ind.begin(), ind.end(),                 [&](int x, int y) { return set[x].size() > set[y].size(); });       for (int i : ind) {         a[i] = 0;         for (int j = 0; j < r; ++j) {           int ex0 = 0, ex1 = 0;           for (long long y : set[i])             ex0 += m[(1 << (j + 1)) + ((y & ((1 << (j + 1)) - 1)) ^ a[i])],                 ex1 += m[(1 << (j + 1)) +                          ((y & ((1 << (j + 1)) - 1)) ^ (a[i] | (1 << j)))];           if (ex1 < ex0) a[i] |= (1 << j);         }         for (long long y : set[i]) {           int v = (g(y) ^ a[i]);           for (int j = 0; j < r; ++j)             m[(1 << (r - j)) + v]++, v = v & ((1 << (r - 1 - j)) - 1);         }       }     }       public:     Map() {}     Map(const std::vector<long long> &S, int word) { init(S, word); }     int operator()(long long x) { return lower(x) ^ B[upper(x) ^ A[lower(x)]]; }     int size() { return (1 << r); }     bool have(long long x) { return who[(*this)(x)] == x; }     int &operator[](long long i) { return val[(*this)(i)]; }     void init(const std::vector<long long> &S, int word) {       n = (int)S.size();       w = word;       r = std::max(w / 2, (int)std::log2(n) + 3) + 1;       assert(*std::min_element(S.begin(), S.end()) >= 0);       assert(*std::max_element(S.begin(), S.end()) < (1ll << word));       lower = [&](long long x) { return x & ((1 << r) - 1); };       upper = [&](long long x) { return x >> (w - r); };       find_array(A, S, lower, upper);       auto f2 = [&](long long x) { return upper(x) ^ A[lower(x)]; };       auto &g2 = lower;       find_array(B, S, f2, g2);       who.resize(1 << r, -1);       for (long long x : S) who[(*this)(x)] = x;       val.resize(1 << r);     }   };   void make_unique(std::vector<long long> &A) {     std::sort(A.begin(), A.end());     A.resize(std::unique(A.begin(), A.end()) - A.begin());   }   int main() {     std::ios_base::sync_with_stdio(false);     std::cin.tie(0);     int n, k;     std::cin >> n >> k;     std::vector<int> A(n);     long long pref = 0;     std::vector<long long> values;     values.push_back(pref);     for (int i = 0; i < n; ++i) {       std::cin >> A[i];       pref += A[i];       values.push_back(pref);     }     make_unique(values);     long long min = *std::min_element(values.begin(), values.end());     std::vector<long long> lower, upper;     for (long long x : values)       lower.push_back((x - min) & ((1 << 24) - 1)),           upper.push_back((x - min) >> 24);     make_unique(lower);     make_unique(upper);     Map ml(lower, 24);     Map mu(upper, 24);     std::vector<long long> vals;     auto kto = [&](long long x) {       if (!ml.have((x - min) & ((1 << 24) - 1)) || !mu.have((x - min) >> 24))         return -1ll;       return ml((x - min) & ((1 << 24) - 1)) +              1ll * ml.size() * mu((x - min) >> 24);     };     for (long long x : values) vals.push_back(kto(x));     make_unique(vals);     Map map(vals, 40);     long long ans = 0;     pref = 0;     map[kto(pref)]++;     for (int i = 0; i < n; ++i) {       pref += A[i];       long long pow = 1;       while (std::abs(pow) < 1000000000ll * 100000ll + 5ll) {         long long want = (pref - pow);         if (want >= min && want <= min + (1ll << 48)) {           if (kto(want) != -1 && map.have(kto(want))) {             ans += map[kto(want)];           }         }         pow *= k;         if (pow == 1) break;       }       map[kto(pref)]++;     }     std::cout << ans <<   n ;     return 0;   }   