Fibonacci

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
#define _for(i, a, b) for(int i = a; i < b; i++)
const int maxn = 105;
const int mod = 100000000;
//1 1 2 3 5 8 13 21 34
template<int row, int col>
struct Matrix{
        Matrix();
        ll ele[row][col];
        Matrix(int a, int b): r(a), c(b) {
            memset(ele, 0, sizeof(ele));
        }
        ll &operator()(int a, int b){
            return ele[a][b];
        }
        Matrix &operator*=(Matrix oth) {
            return *this = *this * oth;
        }
        int r, c;
};

template<int m, int n, int p>
Matrix<m, p> mulmod(Matrix<m, n> m1, Matrix<n, p> m2, int mod)//普通乘法
{
    Matrix<m, p> ret(m1.r, m2.c);
    _for(i, 0, m1.r){
        _for(k, 0, m1.c){
            _for(j, 0, m2.c){
                ret(i, j) = (ret(i, j) + m1(i, k) * m2(k, j) % mod) % mod;
            }
        }
    }
    return ret; 
} 

template<int m, int n>
Matrix<m, n> qpowmod(Matrix<m, n>mat, ll k, int mod){
    Matrix<m, n> ans = mat;
    for(k--; k; mat = mulmod(mat, mat, mod), k >>= 1){
        if(k & 1){
            ans = mulmod(ans, mat, mod);
        }
    }
    return ans;
}

template<int m, int n>
istream &operator>>(istream &is, Matrix<m, n> &mat){
    _for(i, 0, mat.r){
        _for(j, 0, mat.c){
            is >> mat(i, j);
        }
    }
    return is;
} 
template<int m, int n>
ostream &operator<<(ostream &os, Matrix<m, n> &mat){
    _for(i, 0, mat.r){
        _for(j, 0, mat.c){
            os << mat(i, j) << ' ';
        }
        os << endl;
    }
    return os;
}

int main(){
    int n;
    while(cin >> n && n != -1){
        if(n == 0) {
            cout << 0 << endl;
            continue;
        }
        Matrix<maxn, maxn> mat(2, 2);
        mat(0, 0) = 1, mat(0, 1) = 1, mat(1, 0) = 1, mat(1, 1) = 0;
        auto tmp = qpowmod(mat, n, mod);
        cout << tmp(0, 1) << endl;
    }
    return 0;
}