HDU [P5015] 233 Matrix

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#define ll long long
using namespace std;
const int MOD = 10000007;
int n, m;
struct Matrix {
    ll num[15][15];
    void clear() {
        memset(num, 0, sizeof(num));
    }
    void unit() {
        clear();
        for(int i = 0; i <= n + 1; i++) num[i][i] = 1;
    }
    Matrix operator * (const Matrix & b) {
        Matrix ans;
        ans.clear();
        for(int i = 0; i <= n + 1; i++) {
            for(int j = 0; j <= n + 1; j++) {
                ll tmp = 0ll;
                for(int k = 0; k <= n + 1; k++) {
                    tmp += num[i][k] * b.num[k][j];
                }
                ans.num[i][j] = tmp % MOD;
            }
        }
        return ans;
    }
    Matrix operator ^ (ll k) {
        Matrix ans, tt = (*this);
        ans.unit();
        while(k) {
            if(k & 1ll) ans = ans * tt;
            tt = tt * tt;
            k >>= 1;
        }
        return ans;
    }
    void print() {
        for(int i = 0; i <= n + 1; i ++) {
            for(int j = 0; j <= n + 1; j++) {
                printf("%lld ", num[i][j]);
            }
            printf("\n");
        }
    }
};
int main() {
    while(~scanf("%d %d", &n, &m)) {
        Matrix a, b;
        a.clear(); b.clear();
        for(int i = 0; i <= n + 1; i++) {
            if(i <= n) a.num[i][0] = 10; 
            a.num[i][n + 1] = 1;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                a.num[i][j] = 1;
            }
        }
        b.num[0][0] = 23; b.num[n + 1][0] = 3;
        for(int i = 1; i <= n; i++) scanf("%lld", &b.num[i][0]);
        b = (a ^ m) * b;
        cout << b.num[n][0] << endl;
    }
    return 0;
}