func_code_string: #include <bits/stdc++.h>   using namespace std;   int getint() {     int s = 0, o = 1;     char c;     for (c = getchar(); c <  0  || c >  9 ; c = getchar())       if (c ==  - ) o = -1;     for (; c >=  0  && c <=  9 ; c = getchar()) s *= 10, s += c -  0 ;     return s * o;   }   const int mod = (int)1e9 + 7;   struct Mat {     int n;     long long x;     int a[31][31];     void operator*=(const Mat &p) {       int c[31][31];       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++) {           long long r = 0;           for (int k = 0; k < n; k++) r += (1ll * a[i][k] * p.a[k][j]) % mod;           c[i][j] = r % mod;           if (c[i][j] < 0) c[i][j] += mod;         }       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++) a[i][j] = c[i][j];     }     void write() {       for (int i = 0; i < n; i++) {         for (int j = 0; j < n; j++) printf( %d  , a[i][j]);         printf(  n );       }     }   } A[70][30], B[70][30];   long long n;   int k;   Mat I;   Mat calc(int i, int j, long long n) {     Mat r = I;     if (n == 0) return r;     for (int timer = 0; timer < k; timer++) {       if (n >= A[i][j].x)         r *= A[i][j];       else         r *= calc(i - 1, j, n);       n -= A[i][j].x;       if (n <= 0) break;       j = (j + 1) % k;     }     return r;   }   int main(int argc, char const *argv[]) {     scanf( %I64d%d , &n, &k);     I.n = k + 1;     for (int i = 0; i < I.n; i++)       for (int j = 0; j < I.n; j++) I.a[i][j] = i == j;     for (int i = 0; i < k; i++) {       Mat &M = A[0][i];       M.n = k + 1, M.x = 1;       for (int t = 0; t < k + 1; t++)         for (int s = 0; s < k + 1; s++) M.a[t][s] = (t == s || t == i);       Mat &N = B[0][i];       N.n = k + 1, N.x = 1;       for (int t = 0; t < k + 1; t++)         for (int s = 0; s < k + 1; s++) {           if (t == i) N.a[t][s] = -1;           if (t == s) N.a[t][s] = 1;         }     }     int i;     for (i = 0;; i++) {       long long _x = A[i][0].x * k;       if (_x > n || _x < 0) break;       Mat &M = A[i + 1][0];       M = A[i][0];       M.x = _x;       for (int p = 1; p < k; ++p) M *= A[i][p];       for (int j = 1; j < k; ++j) {         Mat &M = A[i + 1][j];         M = B[i][j - 1];         M *= A[i + 1][j - 1];         M *= A[i][j - 1];         M.x = _x;       }       Mat &N = B[i + 1][0];       N = B[i][k - 1];       N.x = _x;       for (int p = k - 2; p >= 0; --p) N *= B[i][p];       for (int j = 1; j < k; ++j) {         Mat &N = B[i + 1][j];         N = B[i][j - 1];         N *= B[i + 1][j - 1];         N *= A[i][j - 1];         N.x = _x;       }     }     Mat res = calc(i, 0, n);     long long r = 0;     for (int i = 0; i < k + 1; i++) r += res.a[i][k];     printf( %I64d n , r % mod);     return 0;   }   