func_code_string: #include <bits/stdc++.h>   using namespace std;   const int maxn = 31;   const int mod = 1000000007;   struct ma {     long long a[maxn][maxn];     int n;     ma(int m = 0) {       n = m;       memset(a, 0, sizeof(a));       for (int i = 0; i < n; i++) a[i][i] = 1;     }     ma(const ma& nn) {       n = nn.n;       memcpy(a, nn.a, sizeof(a));     }     ma operator*(const ma& nn) {       ma ret(n);       memset(ret.a, 0, sizeof(ret.a));       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++) {           for (int k = 0; k < n; k++) ret.a[i][j] += a[i][k] * nn.a[k][j] % mod;           ret.a[i][j] %= mod;         }       return ret;     }   };   ma mypow(ma a, long long n) {     ma ret(a.n);     while (n) {       if (n & 1) ret = ret * a;       n >>= 1;       a = a * a;     }     return ret;   }   ma m1[100], m2[100];   int main() {     long long n;     int k, i, j;     cin >> n >> k;     n--;     m1[1].n = k + 1;     for (i = 0; i <= k; i++) m1[1].a[i][i] = 1;     for (i = 1; i < 99; i++) {       int tmp = ((-i - 1) % k + k) % k + 1;       tmp = k - tmp;       memcpy(m2[i].a[0], m1[i].a[k], sizeof(m1[i].a[k]));       for (j = 1; j <= k; j++) {         for (int c = 0; c <= k; c++)           m2[i].a[j][c] =               ((m2[i].a[j - 1][c] * 2 - m1[i].a[tmp][c]) % mod + mod) % mod;         tmp++;         if (tmp >= k) tmp = 0;       }       m2[i].n = k + 1;       m1[i + 1] = m1[i] * mypow(m2[i], k - 1);     }     ma ans(k + 1);     int ind = 1, sheng = n % k;     n /= k;     while (n) {       ans = ans * mypow(m2[ind], n % k);       ind++, n /= k;     }     long long ret = 0;     for (i = 0; i <= k; i++) ret = (ret + ans.a[sheng + 1][i] * (1ll << i)) % mod;     cout << ret << endl;   }   