func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MOD = 1000000007;   vector<vector<vector<int> > > dp;   vector<vector<int> > tmp;   vector<vector<int> > base;   int get_dig(int pos, int k) {     return (pos < k) ? pos : (get_dig(pos / k, k) + pos % k) % k;   }   inline int get_val(const vector<vector<int> > &a, int i, int j, int shift,                      int k) {     if (i == k && j < k) {       return a[k][(j + k - shift) % k];     }     return a[(i + k - shift) % k][(j + k - shift) % k];   }   vector<vector<int> > shift(const vector<vector<int> > &a, int shift) {     int k = int(a.size()) - 1;     vector<vector<int> > res = a;     for (int i = 0; i <= k; ++i) {       for (int j = 0; j < k; ++j) {         res[i][j] = get_val(a, i, j, shift, k);       }     }     return res;   }   vector<vector<int> > operator*(const vector<vector<int> > &a,                                  const vector<vector<int> > &b) {     int n = int(a.size()), k = int(a[0].size()), m = int(b[0].size());     vector<vector<int> > res(n, vector<int>(m, 0));     for (int i = 0; i < n; ++i) {       for (int j = 0; j < m; ++j) {         for (int l = 0; l < k; ++l) {           res[i][j] = (res[i][j] + 1ll * a[i][l] * b[l][j]) % MOD;         }       }     }     return res;   }   int main() {     long long n;     int k;     cin >> n >> k;     int max_depth = 0;     {       long long tmp = n;       while (tmp != 0) {         ++max_depth;         tmp /= k;       }     }     dp.resize(max_depth);     {       dp[0].assign(k + 1, vector<int>(k + 1, 0));       for (int i = 0; i <= k; ++i) {         for (int j = 0; j <= k; ++j) {           dp[0][i][j] = (i == j || j == 0);         }       }       vector<vector<int> > e(k + 1, vector<int>(k + 1, 0));       for (int i = 0; i <= k; ++i) {         e[i][i] = 1;       }       for (int depth = 1; depth < max_depth; ++depth) {         dp[depth] = e;         vector<vector<int> > bs = dp[depth - 1];         vector<vector<int> > &res = dp[depth];         int curx = k;         for (int i = 0; (1 << i) <= curx; ++i) {           if (curx & (1 << i)) {             res = bs * shift(res, (1 << i));             curx ^= (1 << i);           }           bs = bs * shift(bs, (1 << i));         }       }     }     base.assign(1, vector<int>(k + 1, 0));     base[0][k] = 1;     int sl = 0;     long long x = n;     vector<int> vec;     while (x != 0) {       vec.push_back(x % k);       x /= k;     }     int len = int(vec.size());     for (int cur_depth = len - 1; cur_depth >= 0; --cur_depth) {       int rest = vec[cur_depth];       for (int it = 0; it < rest; ++it, sl = (sl + 1) % k) {         base = base * shift(dp[cur_depth], sl);       }     }     {       int res = 0;       for (int i = 0; i <= k; ++i) {         res = (res + base[0][i]) % MOD;       }       cout << res <<   n ;     }     return 0;   }   