#include <iostream>
#include <climits>
using namespace std;
template <class T>
class Matrix {
public:
int m,n;
T** data;
Matrix(int m, int n, const T &value):m(m),n(n) {
data=new T*[m];
for(int i=0; i<m; i++)
data[i]=new T[n];
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
data[i][j]=value;
}
Matrix<T> operator%(int a) {
Matrix<T> result(m,n,0);
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
result[i][j]=data[i][j]%a;
return result;
}
Matrix<T> operator*(Matrix<T> a) {
Matrix<T> result(m,a.n,0);
for(int i=0; i<m; i++)
for(int j=0; j<a.n; j++)
for(int k=0; k<n; k++)
result[i][j]+=data[i][k]*a[k][j]%10000;
return result;
}
T* operator[](int i) {
return data[i];
}
};
template <class T>
class squareMatrix:public Matrix<T> {
public:
squareMatrix(int n,const T value): Matrix<T>(n,n,value) {}
squareMatrix(const Matrix<T> &a):Matrix<T>(a.m<a.n?a.m:a.n,a.m<a.n?a.m:a.n,0) {
for(int i=0; i<Matrix<T>::m; i++)
for(int j=0; j<Matrix<T>::m; j++)
Matrix<T>::data[i][j]=a.data[i][j];
}
squareMatrix<T> operator^(int a) {
squareMatrix<T> p(this->operator*(*this));
if(a>1)
if(a%2)
return this->operator*(p^(a/2))%10000;
else
return p^(a/2)%10000;
else
return *this;
}
};
int main() {
squareMatrix<int> a(2,1);
a[1][1]=0;
cout<<(a^INT_MAX)[0][0]<<endl;
}